Swap all occurrences of two characters to get lexicographically smallest string

Posted by N.K. Chauhan on Mar 31, 2024

Given a string s of length n, it consists of lowercase English alphabets.

The task is to choose any two characters in the string and replace all the occurences of the first character with the second character and the second character with the first character so that the final string is the lexicographically smallest string that can be obtained by doing this operation at most once.

For example, "abc" is lexicographically smaller than "bac" because 'a' comes before 'b' in dictionary order.

Input: s = "zyxwvu", n = 5
Output: "uyxwvz"

Input: s = "baab", n = 4
Output: "abba"


Solutions

Method 1: In O(n^2) time and O(1) space

In this approach, we need to find two characters such that the left character (c1) should be greater than the right character (c2) and "c2" should not exist left to "c1".

The idea is to iterate over the array from i to n-2 and for each element c1 = arr[i] check if any element c2 = arr[i+1...n-1] fulfils the following conditions:

1) The element c2 should be smallest in sub-array (i...n-1).
2) The element c2 should not exist in sub-array (0...i-1).

If any value is found for c2, iterate over the array again and replace c1 with c2 and c2 with c1.

Complexity

The time complexity of this solution is O(n^2) and space complexity is O(1).

Related


Print all subsequences of a string

Check if two given strings are isomorphic to each other

Reverse words in a given string

Find all substrings of a string in "O (n^2)" time

Check if two strings are equal or not after processing backspace

Print all permutations of a given string

Longest Common Prefix in an Array of Strings

Power Set: Print all non-empty subsequences of a string

Transform One String to Another with a Minimum Number of Operations

Check whether the given string is a palindrome