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.

Description Hints 1 Solution Video 5:09

3216. Lexicographically Smallest String After a Swap

Q: 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.

Easy54.6% acceptance1 company

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.

Asked at 1 company

JPMorgan Chase

Topics

Greedy String

Hints open one at a time

Hint 1

Try all possible swaps satisfying the constraints and find the one that results in the lexicographically smallest string.

5:09

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution