Problem Statement
Given a string S. The task is to find the lexicographically smallest string possible by inserting a given character.
A string a is lexicographically smaller than string b (of the same length) if in the first position where a and b differ, string a has a letter that appears earlier in the alphabet than the corresponding letter in b. For example, “abc” is lexicographically smaller than “bac” because ‘a’ comes before ‘b’ in dictionary order.
Examples:
Confused about your next job?
Input: S = “axc”, ch = ‘b’
Output: abxc
Explanation:
Inserting character b in the second position gives the lexicographically smallest string.
Input: S = “abcd”, ch = ‘e’
Output: abcde
Explanation:
Inserting character e in the last index gives the lexicographically smallest string.
Approach
The approach is to insert the given character just before the position, where the S[i] is lexicographically larger than the character ch.
Algorithm:
- Iterate over the string from i = 0 till i = N.
- If the current character of the string S[i] is lexicographically larger than the character ch, insert the character at that index and terminate the loop.
- Else, continue iterating and if no such character is found which is lexicographically greater than ch, insert ch at the end of the string.
C++ Implementation
Java Implementation
Python Implementation
Time Complexity: O(N), where N is the length of the string.
Space Complexity: O(1), as no extra space is used.
Practice Question
Lexicographically Largest Array
Frequently Asked Questions
What is the lexicographically smallest string?
A string a is lexicographically smaller than string b (of the same length) if in the first position where a and b differ, string a has a letter that appears earlier in the alphabet than the corresponding letter in b
What is the time complexity of the insertion of a character at a given position?
The time complexity of insertion of a character at a given position is O(1).
