Lexicographically Smallest String After a Swap
EasyPrompt
Given a string s containing only digits, return the lexicographically smallest string that can be obtained after swapping adjacent digits in s with the same parity at most once.
Digits have the same parity if both are odd or both are even. For example, 5 and 9, as well as 2 and 4, have the same parity, while 6 and 9 do not.
Example 1:
Input: s = "45320"
Output: "43520"
Explanation:
s[1] == '5' and s[2] == '3' both have the same parity, and swapping them results in the lexicographically smallest string.
Example 2:
Input: s = "001"
Output: "001"
Explanation:
There is no need to perform a swap because s is already the lexicographically smallest.
Constraints:
2 <= s.length <= 100sconsists only of digits.
Approaches
2 approaches with complexity analysis and trade-offs.
This approach systematically generates every possible string that can be created by performing a single valid swap. It then compares all these generated strings, along with the original string, to find the one that is lexicographically smallest.
Algorithm
- Initialize a string variable
smallestStringwith the original strings. - Iterate through the string from
i = 0tos.length() - 2. - For each index
i, check if the digits ats[i]ands[i+1]have the same parity. - If they do, create a new temporary string
tempStringby swapping the characters atiandi+1. - Compare
tempStringwithsmallestString. IftempStringis lexicographically smaller, updatesmallestStringtotempString. - After the loop finishes, return
smallestString.
Walkthrough
The algorithm initializes a variable, say smallestString, with the original string s. It then iterates through all adjacent pairs of characters in the string, from index i = 0 to n-2, where n is the length of the string. For each pair (s[i], s[i+1]), it checks if the two digits have the same parity (both even or both odd). If they do, it creates a new temporary string by swapping these two characters. This new string is then lexicographically compared with the current smallestString. If the new string is smaller, smallestString is updated. After checking all possible adjacent pairs, the final smallestString holds the lexicographically smallest possible string after at most one swap, which is then returned. This method is exhaustive but less efficient because it continues to search for swaps even after a potentially optimal one has been found.
class Solution { public String smallestString(String s) { String smallestString = s; char[] chars = s.toCharArray(); int n = s.length(); for (int i = 0; i < n - 1; i++) { int d1 = chars[i] - '0'; int d2 = chars[i + 1] - '0'; if ((d1 % 2) == (d2 % 2)) { // Create a temporary copy and perform the swap char[] tempChars = s.toCharArray(); char temp = tempChars[i]; tempChars[i] = tempChars[i + 1]; tempChars[i + 1] = temp; String tempString = new String(tempChars); // Update the smallest string found so far if (tempString.compareTo(smallestString) < 0) { smallestString = tempString; } } } return smallestString; }}Complexity
Time
O(N^2), where N is the length of the string. The main loop runs N-1 times. Inside the loop, creating a new string from a character array takes O(N) time, and comparing two strings also takes O(N) time. This leads to a total complexity of O(N * N).
Space
O(N), where N is the length of the string. A character array of size N is used, and for each potential swap, a new temporary string and character array of size N are created.
Trade-offs
Pros
Simple to understand and implement.
Guarantees the correct answer by exhaustively checking all possibilities.
Cons
Inefficient due to its O(N^2) time complexity, which can be slow for larger inputs (though acceptable for the given constraints).
Performs redundant work by checking all possible swaps, even after finding a swap that results in a lexicographically smaller string.
A more efficient approach is to use a greedy strategy. To make a string lexicographically smallest, we want to make the earliest possible character smaller. We can achieve this by finding the first position i where a swap of s[i] and s[i+1] would result in a smaller character at s[i]. Once we find and perform this swap, any subsequent swap would affect a later position, resulting in a lexicographically larger string. Therefore, the first beneficial swap we find is the optimal one.
Algorithm
- Convert the input string
sto a character arraycharsfor easy modification. - Loop
ifrom0tos.length() - 2. - Get the integer values of the digits at
chars[i]andchars[i+1]. - Check if they have the same parity AND if the digit at
iis greater than the digit ati+1. - If both conditions are true, this is the first and best opportunity for a swap.
- Swap
chars[i]andchars[i+1]. - Return the new string created from the modified
charsarray immediately. - If the loop completes without finding any such pair, it means no beneficial swap is possible. Return the original string
s.
Walkthrough
The algorithm iterates through the string from left to right, examining adjacent characters s[i] and s[i+1]. For each pair, it checks two conditions: 1. Do s[i] and s[i+1] have the same parity? 2. Is s[i] greater than s[i+1]? If both conditions are true, it means swapping them will place a smaller digit at index i, making the entire string lexicographically smaller. Since we are iterating from left to right, the first time we find such a pair is the leftmost (and thus most significant) position where we can improve the string. Upon finding this pair, the algorithm performs the swap and immediately returns the new string. If the loop completes without finding any such pair, it implies that no single adjacent swap can make the string smaller. In this case, the original string is already the smallest possible, and it is returned unchanged.
class Solution { public String smallestString(String s) { char[] chars = s.toCharArray(); int n = s.length(); for (int i = 0; i < n - 1; i++) { // Get the integer values of the characters int d1 = chars[i] - '0'; int d2 = chars[i + 1] - '0'; // Check for same parity if ((d1 % 2) == (d2 % 2)) { // Check if swapping makes the string lexicographically smaller if (d1 > d2) { // Swap the characters char temp = chars[i]; chars[i] = chars[i + 1]; chars[i + 1] = temp; // Return the new string immediately as this is the best possible swap return new String(chars); } } } // If no swap was made, return the original string return s; }}Complexity
Time
O(N), where N is the length of the string. The algorithm iterates through the string at most once. If a swap is performed, creating the new string takes O(N) time, and the function returns. In the worst case (no swap), the loop runs N-1 times with constant time operations in each iteration.
Space
O(N). A character array of size N is created to hold the characters of the string. This is necessary because strings are immutable in Java.
Trade-offs
Pros
Highly efficient with a linear time complexity of O(N).
Simple and elegant logic that finds the optimal solution in a single pass.
Cons
The greedy logic, while simple, might not be immediately obvious without understanding the properties of lexicographical ordering.
Solutions
Solution
class Solution {public String getSmallestString(String s) { char[] cs = s.toCharArray(); int n = cs.length; for (int i = 1; i < n; ++i) { char a = cs[i - 1], b = cs[i]; if (a > b && a % 2 == b % 2) { cs[i] = a; cs[i - 1] = b; return new String(cs); } } return s; }}class Solution {public: string getSmallestString(string s) { int n = s.length(); for (int i = 1; i < n; ++i) { char a = s[i - 1], b = s[i]; if (a > b && a % 2 == b % 2) { s[i - 1] = b; s[i] = a; break; } } return s; }};class Solution: def getSmallestString(self, s: str) -> str: for i, (a, b) in enumerate(pairwise(map(ord, s))): if (a + b) % 2 == 0 and a > b: return s[: i] + s[i + 1] + s[i] + s[i + 2:] return sVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.