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 <= 100s consists only of digits.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.
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.
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.
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.
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.
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.
Time Complexity: O(n log n), primarily due to sorting.
Space Complexity: O(n), additional lists for even and odd are used.
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.
| 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. |
| Counting Sort Based Swap | Time Complexity: O(n log n), primarily due to sorting. |
| Greedy + Simulation | — |
| 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. |
3216 Lexicographically Smallest String After a Swap || How to 🤔 in Interview || String 🔥 • Ayush Rao • 986 views views
Watch 6 more video solutions →Practice Lexicographically Smallest String After a Swap with our built-in code editor and test cases.
Practice on FleetCode