Scale Engineer

Lexicographically Smallest String After a Swap

Easy
#2856Time: 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.1 company
Patterns
Greedy
Data structures
String
Companies
J.P. Morgan

Prompt

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 <= 100
  • s consists 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 smallestString with the original string s.
  • Iterate through the string from i = 0 to s.length() - 2.
  • For each index i, check if the digits at s[i] and s[i+1] have the same parity.
  • If they do, create a new temporary string tempString by swapping the characters at i and i+1.
  • Compare tempString with smallestString. If tempString is lexicographically smaller, update smallestString to tempString.
  • 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.

Solutions

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;  }}

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

← Previous

Previous problem

Next →

Next problem