Given a string s of size N consisting of digits from 0 to 9. Discover the lexicographically minimal sequence that may be obtained from given string s by performing the given operations:
- Deciding on any place i within the string and delete the digit ‘d‘ at ith place,
- Insert min(d+1, 9) on any place within the string s.
Enter: s = ” 5217 “
Output: s = ” 1367 “
Select 0th place, d = 5 and insert 6 i.e. min(d+1, 9) between 1 and 7 in string; s = ” 2167 “
Select 0th place, d = 2 and insert 3 i.e. min(d+1, 9) between 1 and 6 in string; s = ” 1367 “
Enter: s = ” 09412 “
Output: s = ” 01259 “
Select 1st place, d = 9 and insert 9 i.e. min(d+1, 9) eventually of string; s = ” 04129 “
Select 1st place, d = 4 and insert 5 i.e. min(d+1, 9) between 2 and 9 in string; s = ” 0 1 2 5 9 “
Strategy: Implement the thought under to unravel the issue:
At every place i, we verify if there’s any digit sj such that sj < si and j > i. As we’d like the lexicographically minimal string, we have to deliver the jth digit forward of ith digit. So delete the ith digit and insert min(si+1, 9) behind the jth digit. In any other case, if no lesser digits are current forward of ith digit, maintain the digit as it’s and don’t carry out the operation.
Comply with the under steps to implement the above thought:
- Create a suffix vector to retailer the minimal digit in the proper a part of ith place within the string.
- Run a loop from N-2 to 0 and retailer the minimal digit discovered until index i from the top. [This can be done by storing suf[i] = min( suf[i+1], s[i] ) ].
- Create a end result vector that can retailer the digits that will likely be current within the remaining lexicographically minimal string.
- Traverse for every place from i = 0 to N-1 within the string and verify if there’s any digit lower than the present digit (d = s[i]-‘0’) on the proper facet:
- If sure then push min(d+1, 9) in end result.
- Else push (d) within the end result.
- Kind the vector end result and print the values [Because we can easily arrange them in that way as there is no constraint on how many times we can perform the operation].
Under is the implementation of the above method:
Time Complexity: O(N * log N)
Auxiliary House: O(N)