A20250415_flipkart_strings

'''
A20250415_flipkart_strings

given you a string
need to make it lexographically smallest string by doing
one operation

operation pick any character and place it anywhere else


-----------------------------------------------------------------------------------------------------
important thing to be noted is

the main nature of lexographic is ,the first characters in the string should be as small as possible
how do we know where to place
lets have a reference of smallest lexographic string
which is obtained by sorting string characters
now compare it with every char of original
when there is a mismatch we know the position now at this point print the ideal character and
from now on continue printing the other
however if you encountered ideal character again through the original string,if it is the last occurance skip it

skipping the last occarance instead of first occurance in problematic part
 will make us to have the smallest possible lexographic string

say you have
BCCCAADAAD //given
AAAABCCCDD //sorted

ABCCCAADAD //ans when we picked right most A
ABCCCADAAD //ans when we picked left most A

so it is evident to choose the right most than the left most A

-----------------------------------------------------------------------------------------------------
input -
BCCCAADAAD

output -
ABCCCADAAD

'''

givenStringArr = list(input())
sortedStringArr = sorted(givenStringArr)
fMap = {}
for char in givenStringArr:
    if char in fMap:
        fMap[char] += 1
    else:
        fMap[char] = 1
firstMismatchFound = False
idealChar = '#'
for i in range(len(givenStringArr)):
    # print('givenStringArr ',givenStringArr[i])
    # print('sortedStringArr ',sortedStringArr[i])
    if not firstMismatchFound and givenStringArr[i] == sortedStringArr[i]:
        print(givenStringArr[i],end='')
        fMap[givenStringArr[i]] -= 1
    elif not firstMismatchFound and givenStringArr[i] != sortedStringArr[i]:
        firstMismatchFound = True
        print(sortedStringArr[i],end='')
        fMap[sortedStringArr[i]] -= 1
        print(givenStringArr[i],end='')
        fMap[givenStringArr[i]] -= 1
    elif firstMismatchFound and fMap[givenStringArr[i]] > 0:
        print(givenStringArr[i],end='')
        fMap[givenStringArr[i]] -= 1