Lexicographically Smallest String After a Swap - Solution & Explanation

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.