Skip to content

3216. Lexicographically Smallest String After a Swap

Description

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.

Solutions

Solution 1: Greedy + Simulation

Thinking

We may swap adjacent same-parity digits at most once. \(n\le 100\) would allow trying every legal swap, but the lexicographically best swap is the leftmost one.

Scan left to right for the first adjacent pair with the same parity and a larger left digit, then swap and stop: a later swap cannot improve an already better prefix. If no such pair exists, the string is already minimal.

We can traverse the string \(\textit{s}\) from left to right. For each pair of adjacent digits, if they have the same parity and the previous digit is greater than the next digit, then we swap these two digits to make the lexicographical order of the string \(\textit{s}\) smaller, and then return the swapped string.

After the traversal, if no swappable pair of digits is found, it means the string \(\textit{s}\) is already in its smallest lexicographical order, and we can return it directly.

The time complexity is \(O(n)\), and the space complexity is \(O(n)\), where \(n\) is the length of the string \(\textit{s}\).

1
2
3
4
5
6
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 s

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
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;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
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;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
func getSmallestString(s string) string {
    cs := []byte(s)
    n := len(cs)
    for i := 1; i < n; i++ {
        a, b := cs[i-1], cs[i]
        if a > b && a%2 == b%2 {
            cs[i-1], cs[i] = b, a
            return string(cs)
        }
    }
    return s
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
function getSmallestString(s: string): string {
    const n = s.length;
    const cs: string[] = s.split('');
    for (let i = 1; i < n; ++i) {
        const a = cs[i - 1];
        const b = cs[i];
        if (a > b && +a % 2 === +b % 2) {
            cs[i - 1] = b;
            cs[i] = a;
            return cs.join('');
        }
    }
    return s;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
impl Solution {
    pub fn get_smallest_string(s: String) -> String {
        let mut cs: Vec<u8> = s.into_bytes();
        let n = cs.len();
        for i in 1..n {
            let (a, b) = (cs[i - 1], cs[i]);
            if a > b && a % 2 == b % 2 {
                cs.swap(i - 1, i);
                return String::from_utf8(cs).unwrap();
            }
        }
        String::from_utf8(cs).unwrap()
    }
}

Comments