Problem

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.

Examples

Example 1

1
2
3
4
5
6
7
8
9


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

1
2
3
4
5
6
7
8
9


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.

Solution

Method 1 – Greedy Swap by Parity

Intuition

To get the lexicographically smallest string, we should swap the first pair of adjacent digits with the same parity where the left digit is greater than the right. This is because only one such swap is allowed, and the earliest such swap will yield the smallest result.

Approach

  1. Iterate through the string from left to right.
  2. For each pair of adjacent digits, if they have the same parity and the left digit is greater than the right, swap them and return the new string.
  3. If no such pair is found, return the original string.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
public:
    string smallestString(string s) {
        int n = s.size();
        for (int i = 0; i < n-1; ++i) {
            if ((s[i]-'0')%2 == (s[i+1]-'0')%2 && s[i] > s[i+1]) {
                swap(s[i], s[i+1]);
                return s;
            }
        }
        return s;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

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

class Solution {
    public String smallestString(String s) {
        char[] arr = s.toCharArray();
        int n = arr.length;
        for (int i = 0; i < n-1; i++) {
            if ((arr[i]-'0')%2 == (arr[i+1]-'0')%2 && arr[i] > arr[i+1]) {
                char tmp = arr[i]; arr[i] = arr[i+1]; arr[i+1] = tmp;
                return new String(arr);
            }
        }
        return s;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
    fun smallestString(s: String): String {
        val arr = s.toCharArray()
        for (i in 0 until arr.size-1) {
            if ((arr[i]-'0')%2 == (arr[i+1]-'0')%2 && arr[i] > arr[i+1]) {
                val tmp = arr[i]; arr[i] = arr[i+1]; arr[i+1] = tmp
                return String(arr)
            }
        }
        return s
    }
}
1
2
3
4
5
6
7
8
9

class Solution:
    def smallestString(self, s: str) -> str:
        arr = list(s)
        n = len(arr)
        for i in range(n-1):
            if int(arr[i])%2 == int(arr[i+1])%2 and arr[i] > arr[i+1]:
                arr[i], arr[i+1] = arr[i+1], arr[i]
                return ''.join(arr)
        return s
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

impl Solution {
    pub fn smallest_string(s: String) -> String {
        let mut arr: Vec<u8> = s.bytes().collect();
        let n = arr.len();
        for i in 0..n-1 {
            if (arr[i]-b'0')%2 == (arr[i+1]-b'0')%2 && arr[i] > arr[i+1] {
                arr.swap(i, i+1);
                return String::from_utf8(arr).unwrap();
            }
        }
        s
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
    smallestString(s: string): string {
        const arr = s.split('');
        for (let i = 0; i < arr.length-1; i++) {
            if (parseInt(arr[i])%2 === parseInt(arr[i+1])%2 && arr[i] > arr[i+1]) {
                [arr[i], arr[i+1]] = [arr[i+1], arr[i]];
                return arr.join('');
            }
        }
        return s;
    }
}

Complexity

  • ⏰ Time complexity: O(n), where n is the length of s. We scan the string once.
  • 🧺 Space complexity: O(n), for the output string or array copy.