3216. Lexicographically Smallest String After a Swap

Intuition

To find the lexicographically smallest string after allowed swaps, we need to carefully consider which adjacent pairs to swap to achieve the smallest possible order.

Approach

1. Convert the String: Convert the string s into a list of characters to facilitate swapping.
2. Iterate and Swap: Traverse through the list and swap adjacent digits if they have the same parity and the first digit is larger than the second.
3. Return the Result: Convert the list back to a string and return it as the result.

Complexity

• Time Complexity: O(n), where n is the length of the string s. This is because we only pass through the string a constant number of times.
• Space Complexity: O(n) due to the storage of the list of characters from string s and the resultant string.

Code

C++

class Solution {
public:
    string getSmallestString(string s) {
        for (int i = 1; i < s.length(); ++i) {
            if ((s[i - 1] & 1) == (s[i] & 1) && s[i - 1] > s[i]) {
                swap(s[i], s[i - 1]);
                break;
            }
        }
        return s;
    }
};

Python

class Solution:
    def getSmallestString(self, s: str) -> str:
        arr = list(s)
        for i in range(1, len(arr)):
            if (int(arr[i - 1]) & 1 == int(arr[i]) & 1) and int(arr[i - 1]) > int(arr[i]):
                arr[i], arr[i - 1] = arr[i - 1], arr[i]
                break
        return "".join(arr)

Java

class Solution {
    public String getSmallestString(String s) {
        char[] arr = s.toCharArray();
        for (int i = 1; i < arr.length; ++i) {
            if ((arr[i - 1] & 1) == (arr[i] & 1) && arr[i - 1] > arr[i]) {
                char temp = arr[i];
                arr[i] = arr[i - 1];
                arr[i - 1] = temp;
                break;
            }
        }
        return new String(arr);
    }
}

JavaScript

var getSmallestString = function (s) {
    var arr = s.split("").map(Number);
    for (var i = 1; i < arr.length; ++i) {
        if ((arr[i - 1] & 1) === (arr[i] & 1) && arr[i - 1] > arr[i]) {
            [arr[i], arr[i - 1]] = [arr[i - 1], arr[i]];
            break;
        }
    }
    return arr.join("");
};