Choose and Swap

Time: O(n)

Space: O(n)

Problem Overview

You may perform one global swap: pick two distinct letters and replace every occurrence of the first with the second and vice versa.

Intuition

You may perform one global swap: pick two distinct letters and replace every occurrence of the first with the second and vice versa. To get the lexicographically smallest result, scan from 'a' upward. The first time the string at index i is not the smallest letter still available, swapping that position's letter with the missing smaller letter is the optimal single swap.

Algorithm

1Count frequency of each lowercase letter.
2Scan letters f from 0 to 25; advance index i past matching letters.
3When freq[f] > 0 and s[i] != (char)(f + 'a'), set first = (char)(f + 'a'), second = s.charAt(i), and break.
4If no pair found, return s.
5Build result swapping every first ↔ second in the string.

Example Walkthrough

Input: s = "ccad"

1. At f = 0 (letter a): i = 0, s[0] = 'c' != 'a'.
2. Swap all a ↔ c: "ccad" → "aacd".
3. That is the best single global swap.

Output: "aacd"

Common Pitfalls

• Swap is global — every occurrence of both letters changes, not just one index.
• If first or second stays '0', the string is already optimal — return s.
• Single-character strings need no swap — return s immediately.

Choose and Swap.java

Java

// Approach: One global swap of two character values (all occurrences) — find the first position where a smaller letter should appear.
// Scan letters a..z; when s[i] != current smallest available letter, swap that letter with s[i] everywhere and return.
// If the string is already lexicographically minimal under one swap, return s unchanged.
// Time: O(n) Space: O(n) for the result string
class Solution {

    public String chooseSwap(String s) {
        int n = s.length();
        if (n == 1) {
            return s;
        }

        int[] freq = new int[26];
        for (char ch : s.toCharArray()) {
            freq[ch - 'a']++;
        }

        char first = '0', second = '0';
        int f = 0, i = 0;

        while (f < 26) {
            if (freq[f] != 0) {

                if (i < n && s.charAt(i) != (char) (f + 'a')) {
                    first = (char) (f + 'a');
                    second = s.charAt(i);
                    break;
                }

                while (i < n && s.charAt(i) == (char) (f + 'a')) {
                    i++;
                }
            }
            f++;
        }
        if (first == '0' || second == '0') {
            return s;
        }

        StringBuilder sb = new StringBuilder();
        for (char ch : s.toCharArray()) {

            if (ch == first) {
                sb.append(second);
            } else if (ch == second) {
                sb.append(first);
            } else {
                sb.append(ch);
            }
        }
        return sb.toString();
    }
}

Was this solution helpful?