Skip to content

3216. Lexicographically Smallest String After a Swap

  • Time: $O(n)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution {
 public:
  string getSmallestString(string s) {
    for (int i = 1; i < s.length(); ++i)
      if (s[i - 1] % 2 == s[i] % 2 && s[i - 1] > s[i]) {
        swap(s[i - 1], s[i]);
        break;
      }
    return s;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution {
  public String getSmallestString(String s) {
    char[] chars = s.toCharArray();
    for (int i = 1; i < chars.length; ++i) {
      if (chars[i - 1] % 2 == chars[i] % 2 && chars[i - 1] > chars[i]) {
        final char temp = chars[i - 1];
        chars[i - 1] = chars[i];
        chars[i] = temp;
        return new String(chars);
      }
    }
    return s;
  }
}

1
2
3
4
5
6
7
8
class Solution:
  def getSmallestString(self, s: str) -> str:
    chars = list(s)
    for i, (a, b) in enumerate(itertools.pairwise(chars)):
      if ord(a) % 2 == ord(b) % 2 and a > b:
        chars[i], chars[i + 1] = chars[i + 1], chars[i]
        return ''.join(chars)
    return s