The "Lexicographically Smallest String After a Swap interview question" allows you to perform at most one swap between two adjacent characters. However, there is a constraint: you can only swap characters if they have the same parity (both even or both odd). Your goal is to find the lexicographically smallest string you can obtain. This "Lexicographically Smallest String After a Swap coding problem" is a focused exercise in greedy decision-making with specific constraints.
This is a common "warm-up" question for roles at companies like J.P. Morgan. it tests a candidate's ability to apply a "Greedy interview pattern" while strictly adhering to parity rules. It evaluates whether you can identify the first opportunity to improve the string's order, which is the hallmark of lexicographical optimization.
The strategy is Greedy. You iterate through the string once and look for the first pair of adjacent characters s[i] and s[i+1] such that they have the same parity AND s[i] > s[i+1]. Swapping these two will immediately make the string lexicographically smaller. Since you only get one swap, you stop as soon as you find and perform this first beneficial swap.
String: "4532"
Lexicographical smallest problems usually mean you want to change the leftmost possible character to something smaller. Always look for the first violation of ascending order that you have the power to fix.
