Make the String lexicographically larger

Given a string str of length n. The task is to find a lexicographic largest string where you are allowed to shift one character from str to any other index only one time.

Examples:

Input: n = 3, str = “bac”
Output: “cba”
Explanation: We can perform the given operation exactly one time on the string str and make many strings. Among them “cba” is lexicographically greater.

Input: n = 6, str = “bacatf”
Output: tbacaf

 Approach: This can be solved with the following idea:

The approach finds the leftmost occurrence of the greatest character and swaps it with the character immediately to its left if it is lesser than the greatest element. This operation ensures that the resulting string is lexicographically larger than the original string. The approach uses the fact that swapping two adjacent characters in a string can only increase its lexicographic order if the character on the left is greater than the character on the right.

Steps involved in the implementation of the code:

• Read the input values of the length of the string, n, and the string itself, str.
• Find the greatest character, ch, in the string s.
• Traverse the string s from left to right and find the leftmost occurrence of the greatest character ch in s.
• If the leftmost occurrence is at the beginning of the string, the string is already lexicographically largest, and no operation is required. In this case, print the string s and move to the next test case.
• Iterate over the string and find where the greatest character appears first from the left from there we can travel to the beginning and swap the letter when the character just left of the ch is lesser than it, either break the loop and return the string.

Below are the steps involved in the implementation of the code:

Time Complexity: O(N)
Auxiliary Space: O(1)

Given a string str of length n. The task is to find a lexicographic largest string where you are allowed to shift one character from str to any other index only one time.

Examples:

Input: n = 3, str = “bac”
Output: “cba”
Explanation: We can perform the given operation exactly one time on the string str and make many strings. Among them “cba” is lexicographically greater.

Input: n = 6, str = “bacatf”
Output: tbacaf

 Approach: This can be solved with the following idea:

The approach finds the leftmost occurrence of the greatest character and swaps it with the character immediately to its left if it is lesser than the greatest element. This operation ensures that the resulting string is lexicographically larger than the original string. The approach uses the fact that swapping two adjacent characters in a string can only increase its lexicographic order if the character on the left is greater than the character on the right.

Steps involved in the implementation of the code:

• Read the input values of the length of the string, n, and the string itself, str.
• Find the greatest character, ch, in the string s.
• Traverse the string s from left to right and find the leftmost occurrence of the greatest character ch in s.
• If the leftmost occurrence is at the beginning of the string, the string is already lexicographically largest, and no operation is required. In this case, print the string s and move to the next test case.
• Iterate over the string and find where the greatest character appears first from the left from there we can travel to the beginning and swap the letter when the character just left of the ch is lesser than it, either break the loop and return the string.

Below are the steps involved in the implementation of the code:

Time Complexity: O(N)
Auxiliary Space: O(1)