Rearrange Letters So No Two Neighbors Match

Medium25–30 min

Topics

HeapGreedyStringHash Table

Companies

AmazonGoogleMicrosoft

Rearrange the letters of a string so that no two equal letters are next to each other. Because many arrangements can be valid, this problem asks for one specific arrangement — the one built greedily: at every position, take the letter with the most unused copies among the letters different from the one just placed, and break ties toward the alphabetically smaller letter. If at some position nothing different is available, no valid arrangement exists and the answer is the empty string.

A max-heap of (copies, letter) with a one-step cool-down for the letter just placed carries out that rule in O(log 26) per position, instead of scanning all 26 letters each time.

Test Case 1:

Input:s = "ddccb"

Output:"cdbcd"

Explanation:c and d tie on 2 copies so c goes first. Then d (2 left, and ≠ c). Then c and b tie on 1 with d just used: b is alphabetically smaller. Then c, then d.

Test Case 2:

Input:s = "nnnoo"

Output:"nonon"

Explanation:n (3 copies) first, then o, then n, then o, then the last n — the letters alternate perfectly.

Test Case 3:

Input:s = "hhhhij"

Output:""

Explanation:Four h's need at least three other letters to keep them apart, but only i and j exist. After h, i, h, j, h there is still an h left with nothing to separate it — return the empty string.

Constraints

◆1 ≤ s.length ≤ 30, s contains only lowercase English letters
◆Build the result one character at a time. At every position, append the letter that has the MOST copies still unused among the letters different from the one just appended; if several letters tie, append the alphabetically smaller one.
◆If at some position no letter different from the previous one has copies left, no valid arrangement exists — return the empty string ""
◆Otherwise return the arrangement built by that rule (it always has no two equal neighbors)

🚀

Try the Dry Run

Don't just read the solution — watch it execute, one step at a time.

Approach & Solutions

Brute Force — Scan All 26 Letters at Every Position

Brute

Keep a count of unused copies per letter. For each position, scan the whole alphabet: skip the letter just used and any letter with no copies left, and among the rest pick the one with the most copies (the first such letter in alphabetical order wins ties, because only a strictly larger count replaces the current best). If the scan finds nothing, no arrangement is possible. It is correct, but every single position pays for a full 26-letter scan.

TimeO(26 · n)

SpaceO(1) extra

Java

Try it out

class Solution {
    public String rearrangeLetters(String s) {
        int[] counts = new int[26];
        for (char ch : s.toCharArray()) counts[ch - 'a']++;
        StringBuilder result = new StringBuilder();
        int previous = -1;
        for (int position = 0; position < s.length(); position++) {
            int best = -1;
            for (int letter = 0; letter < 26; letter++) {
                if (letter == previous || counts[letter] == 0) continue;
                if (best == -1 || counts[letter] > counts[best]) best = letter;
            }
            if (best == -1) return "";
            result.append((char) ('a' + best));
            counts[best]--;
            previous = best;
        }
        return result.toString();
    }
}

Optimal — Max-Heap With a One-Step Cool-Down

Optimal

Put every letter with copies left into a max-heap ordered by (most copies first, then alphabetical). Repeatedly pop the top letter and append it, then use up one copy. The letter just used must not be chosen next, so it is held out of the heap for exactly one step and returned to the heap (if it still has copies) right after the following letter is popped. Each step costs O(log 26) heap work instead of a 26-letter scan. If the heap runs dry while the held letter still has copies, the arrangement is impossible and the result is shorter than the input.

TimeO(n log 26)