Lexicographically Smallest String

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:

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).