Problem of The Day: Lexicographically Smallest String After a Swap

2 min read 560 words

Problem Statement

leetcode problem link

Solution [accepted]

class Solution:
    def getSmallestString(self, s: str) -> str:
        res = list(s)
        for i in range(1, len(s)):
            x = int(s[i - 1])
            y = int(s[i])
            if x % 2 == y % 2:
                if x > y:
                    res[i], res[i - 1] = res[i - 1], res[i]
                    return ''.join(res)

        return s

public class Solution {
    public string GetSmallestString(string s) {
        StringBuilder sb = new StringBuilder(s);
        for (int i = 1; i < s.Length; i++) {
            var x = s[i - 1] - '0';
            var y = s[i] - '0';
            if (x % 2 == y % 2 && x > y) {
                var temp = sb[i- 1];
                sb[i - 1] = sb[i];
                sb[i] = temp;
                return sb.ToString();
            }
        }
        return s;
    }
}

public class Solution {
    public string GetSmallestString(string s) {
        int n = s.Length;
        for (int i = 0; i < n - 1; i++) {
            char a = s[i];
            char b = s[i + 1];

            // Check parity: (a ^ b) & 1 == 0 is a faster way to check if both are even or both odd
            if (a > b && (a % 2 == b % 2)) {
                // Only allocate memory if a swap is actually needed
                char[] arr = s.ToCharArray();
                arr[i] = b;
                arr[i + 1] = a;
                return new string(arr);
            }
        }
        return s;
    }
}