Lexicographically Smallest String After a Swap

Lexicographically Smallest String After a Swap - Problem

String Greedy Easy

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.

Input & Output

Example 1 — Basic Swap

$ Input: s = "4321"

› Output: "4312"

💡 Note: We can swap 2 and 1 (both even) to get "4312", which is lexicographically smaller than the original

Example 2 — No Beneficial Swap

$ Input: s = "1234"

› Output: "1234"

💡 Note: Already in ascending order. Any adjacent same-parity swap would make it lexicographically larger

Example 3 — Multiple Options

$ Input: s = "8742"

› Output: "2748"

💡 Note: Can swap 8 and 7 (no - different parity), 7 and 4 (no - different parity), or 4 and 2 (yes - both even). Best result is swapping 8 and 4 for "4782", but we can only swap adjacent digits, so we get "8724". Actually, we can swap 4 and 2 to get "8742" → "8724". Wait, let me recalculate: 8 (even) can't swap with 7 (odd), 7 (odd) can't swap with 4 (even), 4 (even) can swap with 2 (even) giving "8724". But this makes it larger. So result is "8742".

Constraints

1 ≤ s.length ≤ 10⁵
s consists of digits only

Visualization

Tap to expand

Understanding the Visualization

Input

String of digits with potential same-parity adjacent pairs

Find Swap

Locate first beneficial adjacent same-parity swap

Result

Lexicographically smallest string after at most one swap

Key Takeaway

🎯 Key Insight: Since we can only swap once, the first beneficial adjacent same-parity swap gives the optimal result

Asked in

G Google 25 M Microsoft 18 a Amazon 15

The key insight is that since we can only swap once, we should make the first beneficial adjacent swap that improves lexicographical order. The optimal approach uses a greedy strategy scanning left to right. Time: O(n), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Greedy - First Beneficial Swap	O(n)	O(n)	Scan left to right and perform the first swap that improves lexicographical order
Brute Force - Try All Swaps	O(n²)	O(n)	Try every possible adjacent swap and return the lexicographically smallest result

Greedy - First Beneficial Swap — Algorithm Steps

Iterate through adjacent pairs from left to right
Check if digits have same parity and swapping improves order
Perform the first beneficial swap found
Return the result immediately

Visualization

Tap to expand

Step-by-Step Walkthrough

Scan

Check each adjacent pair from left to right

Found

First pair where smaller digit can move left

Swap

Perform swap and return immediately

Code -

solution.c — C

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

char* solution(char* s) {
    int len = strlen(s);
    char* result = malloc((len + 1) * sizeof(char));
    strcpy(result, s);
    
    for (int i = 0; i < len - 1; i++) {
        if ((result[i] - '0') % 2 == (result[i + 1] - '0') % 2 && 
            result[i + 1] < result[i]) {
            char temp = result[i];
            result[i] = result[i + 1];
            result[i + 1] = temp;
            break;
        }
    }
    
    return result;
}

int main() {
    char s[1001];
    fgets(s, sizeof(s), stdin);
    s[strcspn(s, "\n")] = 0;
    
    char* result = solution(s);
    printf("%s\n", result);
    free(result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass through the string, early termination on first beneficial swap

✓ Linear Growth

Space Complexity

O(n)

Convert string to character array for swapping

⚡ Linearithmic Space

25.0K Views

Medium Frequency

~15 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Greedy - First Beneficial Swap — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler