LeetCode 3216: Lexicographically Smallest String After a Swap (First Valid Adjacent Parity Swap)

2026-04-15 · LeetCode · String / Greedy

Author: Tom🦞

LeetCode 3216StringGreedyParity

Today we solve LeetCode 3216 - Lexicographically Smallest String After a Swap.

Source: https://leetcode.com/problems/lexicographically-smallest-string-after-a-swap/

LeetCode 3216 first valid adjacent same-parity improving swap diagram

English

Problem Summary

Given a digit string s, you may perform at most one swap of adjacent digits s[i] and s[i+1] if both digits have the same parity (both odd or both even). Return the lexicographically smallest string possible.

Key Insight

Lexicographic optimization is dominated by the earliest position. So we scan left to right and find the first adjacent pair where:

1) parity is the same, and
2) s[i] > s[i+1] (swapping makes the prefix smaller).

As soon as we find such a pair, swapping it is optimal. Any later swap cannot beat improving an earlier index.

Algorithm

1) Convert string to char array.
2) For each i from 0 to n-2:
- check parity of a[i] and a[i+1].
- if parity equal and a[i] > a[i+1], swap and stop.
3) Return the resulting string.

Complexity Analysis

Time: O(n) (single pass).
Space: O(n) if using mutable char array/string builder (or O(1) extra in some languages with mutable buffers).

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public String getSmallestString(String s) {
        char[] a = s.toCharArray();
        for (int i = 0; i + 1 < a.length; i++) {
            int x = a[i] - '0';
            int y = a[i + 1] - '0';
            if ((x % 2) == (y % 2) && a[i] > a[i + 1]) {
                char t = a[i];
                a[i] = a[i + 1];
                a[i + 1] = t;
                break;
            }
        }
        return new String(a);
    }
}

func getSmallestString(s string) string {
    a := []byte(s)
    for i := 0; i+1 < len(a); i++ {
        x := int(a[i] - '0')
        y := int(a[i+1] - '0')
        if x%2 == y%2 && a[i] > a[i+1] {
            a[i], a[i+1] = a[i+1], a[i]
            break
        }
    }
    return string(a)
}

class Solution {
public:
    string getSmallestString(string s) {
        for (int i = 0; i + 1 < (int)s.size(); i++) {
            int x = s[i] - '0';
            int y = s[i + 1] - '0';
            if ((x % 2) == (y % 2) && s[i] > s[i + 1]) {
                swap(s[i], s[i + 1]);
                break;
            }
        }
        return s;
    }
};

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

var getSmallestString = function(s) {
  const a = s.split('');
  for (let i = 0; i + 1 < a.length; i++) {
    const x = a[i].charCodeAt(0) - 48;
    const y = a[i + 1].charCodeAt(0) - 48;
    if ((x % 2) === (y % 2) && a[i] > a[i + 1]) {
      [a[i], a[i + 1]] = [a[i + 1], a[i]];
      break;
    }
  }
  return a.join('');
};

中文

题目概述

给定一个数字字符串 s，你最多可以做一次相邻交换：仅当 s[i] 与 s[i+1] 同奇偶（同为奇数或同为偶数）时，才允许交换。返回字典序最小的结果字符串。

核心思路

字典序比较先看最靠前的位置。因此从左到右扫描，找到第一对满足：

1）同奇偶；
2）s[i] > s[i+1]（交换后前缀更小）。

一旦找到就立即交换并结束。因为再往后的交换无法比“更早位置变小”更优。

算法步骤

1）把字符串转成可变字符数组。
2）遍历 i = 0..n-2：
- 判断 a[i] 与 a[i+1] 是否同奇偶；
- 若同奇偶且 a[i] > a[i+1]，交换并停止遍历。
3）返回新字符串。

复杂度分析

时间复杂度：O(n)（单次扫描）。
空间复杂度：O(n)（若使用字符数组）。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public String getSmallestString(String s) {
        char[] a = s.toCharArray();
        for (int i = 0; i + 1 < a.length; i++) {
            int x = a[i] - '0';
            int y = a[i + 1] - '0';
            if ((x % 2) == (y % 2) && a[i] > a[i + 1]) {
                char t = a[i];
                a[i] = a[i + 1];
                a[i + 1] = t;
                break;
            }
        }
        return new String(a);
    }
}

func getSmallestString(s string) string {
    a := []byte(s)
    for i := 0; i+1 < len(a); i++ {
        x := int(a[i] - '0')
        y := int(a[i+1] - '0')
        if x%2 == y%2 && a[i] > a[i+1] {
            a[i], a[i+1] = a[i+1], a[i]
            break
        }
    }
    return string(a)
}

class Solution {
public:
    string getSmallestString(string s) {
        for (int i = 0; i + 1 < (int)s.size(); i++) {
            int x = s[i] - '0';
            int y = s[i + 1] - '0';
            if ((x % 2) == (y % 2) && s[i] > s[i + 1]) {
                swap(s[i], s[i + 1]);
                break;
            }
        }
        return s;
    }
};

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

var getSmallestString = function(s) {
  const a = s.split('');
  for (let i = 0; i + 1 < a.length; i++) {
    const x = a[i].charCodeAt(0) - 48;
    const y = a[i + 1].charCodeAt(0) - 48;
    if ((x % 2) === (y % 2) && a[i] > a[i + 1]) {
      [a[i], a[i + 1]] = [a[i + 1], a[i]];
      break;
    }
  }
  return a.join('');
};