3216. Lexicographically Smallest String After a Swap

The 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.

Example 1:

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:

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.

Approach overview

Problem Overview: You are given a numeric string. You can perform one swap between adjacent digits only if both digits have the same parity (both even or both odd). The goal is to return the lexicographically smallest string possible after at most one such swap.

Approach 1: Greedy Adjacent Swap (O(n) time, O(1) space)

Scan the string from left to right and check every adjacent pair s[i] and s[i+1]. A swap is valid only when both digits have the same parity and s[i] > s[i+1]. The first time you encounter such a pair, swapping them immediately produces the smallest possible lexicographic result. The reason is simple: lexicographic order is determined by the earliest differing position, so improving the leftmost position gives the maximum benefit. Perform the swap and return the string. If no such pair exists, the original string is already optimal.

This greedy rule works because any later swap would affect a less significant position and therefore cannot produce a smaller overall string. The algorithm performs a single pass through the string, checking parity using a simple digit modulo operation. This keeps the solution linear and constant in memory. The strategy relies on properties of Greedy decision making and sequential scanning of a String.

Approach 2: Counting-Sort Inspired Digit Check (O(n) time, O(1) space)

Since digits range from 0–9, you can think of the problem through a counting perspective. As you iterate through the string, evaluate adjacent digits and determine whether a smaller digit of the same parity can move left through a single swap. Instead of explicitly sorting, the method leverages the limited digit range and parity classification (odd vs even) to quickly identify whether swapping the pair would improve lexicographic order.

This approach conceptually mirrors counting sort logic where digits are grouped and compared based on value buckets. For each pair, check parity equivalence and whether the right digit is smaller than the left. Once found, perform the swap and stop. While the mechanics resemble the greedy approach, thinking about digits as buckets can simplify reasoning when extending similar problems involving digit constraints or parity grouping.

Recommended for interviews: The greedy single-pass solution is what interviewers expect. It shows you understand lexicographic ordering and how to optimize with an early decision. Mentioning the counting or bucket perspective demonstrates deeper understanding of digit constraints and patterns commonly used in array and string optimization problems.

Approach 1: Greedy Approach

This approach involves iterating through the string once and looking for an opportunity to swap two adjacent digits of the same parity to obtain a smaller string. By iterating from left to right, and performing the swap as soon as possible, we ensure that the result is lexicographically minimal.

Python

def smallestStringAfterSwap(s):
    n = len(s)
    s = list(s)
    
    def parity(digit):
        return int(digit) % 2
    
    for i in range(n - 1):
        if s[i] > s[i + 1] and parity(s[i]) == parity(s[i + 1]):
            s[i], s[i + 1] = s[i + 1], s[i]
            break
    return ''.join(s)

# Example usage
print(smallestStringAfterSwap('45320'))  # Output: '43520'

Java

public class SmallestString {
    public static String smallestStringAfterSwap(String s) {
        char[] chars = s.toCharArray();
        for (int i = 0; i < chars.length - 1; i++) {
            if (chars[i] > chars[i + 1] && (chars[i] % 2 == chars[i + 1] % 2)) {
                char temp = chars[i];
                chars[i] = chars[i + 1];
                chars[i + 1] = temp;
                break;
            }
        }
        return new String(chars);
    }

    public static void main(String[] args) {
        System.out.println(smallestStringAfterSwap("45320"));  // Output: "43520"
    }
}

C++

#include <iostream>
#include <string>
using namespace std;

string smallestStringAfterSwap(string s) {
    int n = s.length();
    for (int i = 0; i < n - 1; ++i) {
        if (s[i] > s[i + 1] && (s[i] % 2 == s[i + 1] % 2)) {
            swap(s[i], s[i + 1]);
            break;
        }
    }
    return s;
}

int main() {
    cout << smallestStringAfterSwap("45320") << endl;  // Output: "43520"
    return 0;
}

JavaScript

function smallestStringAfterSwap(s) {
    let chars = s.split('');
    for (let i = 0; i < chars.length - 1; i++) {
        if (chars[i] > chars[i + 1] && (chars[i] % 2 === chars[i + 1] % 2)) {
            [chars[i], chars[i + 1]] = [chars[i + 1], chars[i]];
            break;
        }
    }
    return chars.join('');
}

console.log(smallestStringAfterSwap('45320')); // Output: '43520'

#include <stdio.h>
#include <string.h>

char* smallestStringAfterSwap(char* s) {
    int n = strlen(s);
    for (int i = 0; i < n - 1; ++i) {
        if (s[i] > s[i + 1] && (s[i] % 2 == s[i + 1] % 2)) {
            char temp = s[i];
            s[i] = s[i + 1];
            s[i + 1] = temp;
            break;
        }
    }
    return s;
}

int main() {
    char s[] = "45320";
    printf("%s\n", smallestStringAfterSwap(s));  // Output: "43520"
    return 0;
}

using System;

public class SmallestString {
    public static string SmallestStringAfterSwap(string s) {
        char[] chars = s.ToCharArray();
        for (int i = 0; i < chars.Length - 1; i++) {
            if (chars[i] > chars[i + 1] && (chars[i] % 2 == chars[i + 1] % 2)) {
                char temp = chars[i];
                chars[i] = chars[i + 1];
                chars[i + 1] = temp;
                break;
            }
        }
        return new string(chars);
    }

    public static void Main() {
        Console.WriteLine(SmallestStringAfterSwap("45320"));  // Output: "43520"
    }
}

The function smallestStringAfterSwap converts the input string into a list to enable in-place swaps. It then iterates through the string, checking if a swap between two adjacent digits of the same parity will result in a lexicographically smaller string. If a suitable pair is found, they are swapped, and the loop breaks.

Complexity

Time Complexity: O(n), where n is the length of the string, as it involves a single pass through the string.
Space Complexity: O(1), since the swaps are done in place.

Try this approach in the editor

Approach 2: Counting Sort Based Swap

This approach involves utilizing a counting technique to manage odd and even parity digits separately, making use of the small range of digits (0-9). We can implement a modified counting sort to manage odd and even numbers independently to determine the smallest valid configuration without violating parity constraints.

Python

def smallestStringAfterSwapCounting(s):
    odds, evens = [], []
    for digit in s:
        if int(digit) % 2 == 0:
            evens.append(digit)
        else:
            odds.append(digit)
    evens.sort()
    odds.sort()

    result = []
    evens_idx, odds_idx = 0, 0
    for digit in s:
        if int(digit) % 2 == 0:
            result.append(evens[evens_idx])
            evens_idx += 1
        else:
            result.append(odds[odds_idx])
            odds_idx += 1

    return ''.join(result)

# Example usage
print(smallestStringAfterSwapCounting('45320'))  # Output: '43520'

Java

import java.util.*;

public class CountingSortSwap {
    public static String smallestStringAfterSwapCounting(String s) {
        List<Character> odds = new ArrayList<>();
        List<Character> evens = new ArrayList<>();
        for (char c : s.toCharArray()) {
            if ((c - '0') % 2 == 0) evens.add(c);
            else odds.add(c);
        }
        Collections.sort(odds);
        Collections.sort(evens);

        StringBuilder result = new StringBuilder();
        int oddIdx = 0, evenIdx = 0;
        for (char c : s.toCharArray()) {
            if ((c - '0') % 2 == 0) result.append(evens.get(evenIdx++));
            else result.append(odds.get(oddIdx++));
        }
        return result.toString();
    }

    public static void main(String[] args) {
        System.out.println(smallestStringAfterSwapCounting("45320"));  // Output: "43520"
    }
}

C++

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

string smallestStringAfterSwapCounting(string s) {
    vector<char> odds, evens;
    for (char digit : s) {
        if ((digit - '0') % 2 == 0) {
            evens.push_back(digit);
        } else {
            odds.push_back(digit);
        }
    }
    sort(evens.begin(), evens.end());
    sort(odds.begin(), odds.end());

    int even_idx = 0, odd_idx = 0;
    for (int i = 0; i < s.size(); ++i) {
        if ((s[i] - '0') % 2 == 0) {
            s[i] = evens[even_idx++];
        } else {
            s[i] = odds[odd_idx++];
        }
    }
    return s;
}

int main() {
    cout << smallestStringAfterSwapCounting("45320") << endl;  // Output: "43520"
    return 0;
}

JavaScript

function smallestStringAfterSwapCounting(s) {
    let evens = [], odds = [];
    for (let digit of s) {
        (parseInt(digit) % 2 === 0 ? evens : odds).push(digit);
    }
    evens.sort();
    odds.sort();

    let result = '', even_idx = 0, odd_idx = 0;
    for (let digit of s) {
        if (parseInt(digit) % 2 === 0) {
            result += evens[even_idx++];
        } else {
            result += odds[odd_idx++];
        }
    }
    return result;
}

console.log(smallestStringAfterSwapCounting('45320'));  // Output: '43520'

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

int cmp(const void *a, const void *b) {
    return (*(char *)a) - (*(char *)b);
}

char* smallestStringAfterSwapCounting(char* s) {
    int len = strlen(s);
    char odds[len], evens[len];
    int odd_count = 0, even_count = 0;
    for(int i = 0; i < len; i++) {
        if((s[i] - '0') % 2 == 0) {
            evens[even_count++] = s[i];
        } else {
            odds[odd_count++] = s[i];
        }
    }
    qsort(evens, even_count, sizeof(char), cmp);
    qsort(odds, odd_count, sizeof(char), cmp);

    char* result = (char*)malloc(len + 1);
    int even_idx = 0, odd_idx = 0;
    for(int i = 0; i < len; i++) {
        if((s[i] - '0') % 2 == 0) {
            result[i] = evens[even_idx++];
        } else {
            result[i] = odds[odd_idx++];
        }
    }
    result[len] = '\0';
    return result;
}

int main() {
    char s[] = "45320";
    printf("%s\n", smallestStringAfterSwapCounting(s));  // Output: "43520"
    return 0;
}

using System;
using System.Collections.Generic;

public class CountingSortSwap {
    public static string SmallestStringAfterSwapCounting(string s) {
        List<char> odds = new List<char>();
        List<char> evens = new List<char>();
        foreach (char c in s) {
            if ((c - '0') % 2 == 0) evens.Add(c);
            else odds.Add(c);
        }
        odds.Sort();
        evens.Sort();

        char[] result = new char[s.Length];
        int evenIdx = 0, oddIdx = 0;
        for (int i = 0; i < s.Length; i++) {
            if ((s[i] - '0') % 2 == 0) result[i] = evens[evenIdx++];
            else result[i] = odds[oddIdx++];
        }

        return new string(result);
    }

    public static void Main() {
        Console.WriteLine(SmallestStringAfterSwapCounting("45320"));  // Output: "43520"
    }
}

The function smallestStringAfterSwapCounting processes the input string by separating the digits into odd and even lists, sorting these lists to attempt the smallest lexicographical order, and reconstructing the string preserving original par positions. The original adjacency rule indirectly holds as each new list gets rebuilt in old order.

Complexity

Time Complexity: O(n log n), primarily due to sorting.
Space Complexity: O(n), additional lists for even and odd are used.

Try this approach in the editor

Approach 3: Greedy + Simulation

We can traverse the string s from left to right. For each pair of adjacent digits, if they have the same parity and the previous digit is greater than the next digit, then we swap these two digits to make the lexicographical order of the string s smaller, and then return the swapped string.

After the traversal, if no swappable pair of digits is found, it means the string s is already in its smallest lexicographical order, and we can return it directly.

The time complexity is O(n), and the space complexity is O(n), where n is the length of the string s.

TypeScript

function getSmallestString(s: string): string {
    const n = s.length;
    const cs: string[] = s.split('');
    for (let i = 1; i < n; ++i) {
        const a = cs[i - 1];
        const b = cs[i];
        if (a > b && +a % 2 === +b % 2) {
            cs[i - 1] = b;
            cs[i] = a;
            return cs.join('');
        }
    }
    return s;
}

func getSmallestString(s string) string {
	cs := []byte(s)
	n := len(cs)
	for i := 1; i < n; i++ {
		a, b := cs[i-1], cs[i]
		if a > b && a%2 == b%2 {
			cs[i-1], cs[i] = b, a
			return string(cs)
		}
	}
	return s
}

Rust

impl Solution {
    pub fn get_smallest_string(s: String) -> String {
        let mut cs: Vec<u8> = s.into_bytes();
        let n = cs.len();
        for i in 1..n {
            let (a, b) = (cs[i - 1], cs[i]);
            if a > b && a % 2 == b % 2 {
                cs.swap(i - 1, i);
                return String::from_utf8(cs).unwrap();
            }
        }
        String::from_utf8(cs).unwrap()
    }
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Greedy Approach	Time Complexity: O(n), where n is the length of the string, as it involves a single pass through the string. Space Complexity: O(1), since the swaps are done in place.
Counting Sort Based Swap	Time Complexity: O(n log n), primarily due to sorting. Space Complexity: O(n), additional lists for even and odd are used.
Greedy + Simulation	–

Complexity analysis

Approach	Time	Space	When to Use
Greedy Adjacent Swap	O(n)	O(1)	Best general solution. Single pass finds the earliest beneficial swap.
Counting-Sort Inspired Check	O(n)	O(1)	Useful when reasoning about digit ranges and parity buckets.

Frequently asked questions

Is Lexicographically Smallest String After a Swap easy or hard?

The problem is categorized as Easy because it requires only a single pass and a straightforward greedy observation. Once you recognize that the earliest valid swap yields the smallest lexicographic improvement, the implementation becomes simple.

Lexicographically Smallest String After a Swap Python/Java solution

In both Python and Java, the implementation converts the string into a mutable structure (like a character list or array), scans adjacent pairs, and swaps the first pair that satisfies the parity and ordering condition. The logic remains O(n) and identical across languages.

How to solve Lexicographically Smallest String After a Swap in O(n)?

Iterate through the string from left to right and inspect adjacent digits. For each pair, check whether both digits share the same parity and whether the left digit is greater than the right. When this condition is satisfied, swap the two digits and return the result immediately. If no valid improving pair exists, return the original string.

What is the best approach for Lexicographically Smallest String After a Swap?

The best approach is a greedy single-pass scan. Traverse the string and check each adjacent pair of digits. If the digits have the same parity and the left digit is larger than the right digit, swap them immediately. This produces the smallest lexicographic result because improving the earliest position has the largest impact.

Is Lexicographically Smallest String After a Swap asked at Google/Amazon/Meta?

Problems involving lexicographic ordering, greedy swaps, and digit manipulation frequently appear in interviews at companies like Amazon, Google, and Meta. While this exact question may vary slightly, the pattern of identifying the earliest beneficial swap is a common interview concept.

What data structure is used in Lexicographically Smallest String After a Swap?

The solution primarily operates directly on a string or character array. No complex data structures are required. The algorithm relies on sequential scanning, simple digit comparisons, and parity checks using modulo operations.

What is the time complexity of Lexicographically Smallest String After a Swap?

The optimal solution runs in O(n) time where n is the length of the string. The algorithm scans the string once and performs at most one swap. Space complexity is O(1) since the operation is done in-place without additional data structures.

Lexicographically Smallest String After a Swap solution and explanation

The problem

Approach overview

Approach 1: Greedy Approach

Approach 2: Counting Sort Based Swap

Approach 3: Greedy + Simulation

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Lexicographically Smallest String After a Swap solution and explanation

The problem

Approach overview

Approach 1: Greedy Approach

Approach 2: Counting Sort Based Swap

Approach 3: Greedy + Simulation

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems