Reorganize String

Medium Arrays & Hashing Greedy Original on LeetCode

Reorganize String is a medium arrays & hashing problem solved with the greedy pattern. The best approach, optimal (fill even slots, then odd slots), runs in O(n) time and O(n) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from greedy (most frequent allowed letter) up.

Problem

You are given a string s of lowercase letters. Rearrange its characters so that no two neighbouring characters are the same, and return the rearranged string.

If no such arrangement exists, return the empty string "". When several arrangements work, any one of them is accepted.

Examples

Example 1

Input
s = "mmn"
Output
"mnm"
Why
The two m's are split by the n, so no two neighbours match.

Example 2

Input
s = "zzzy"
Output
""
Why
Three z's need at least two other letters between them, but only one y exists.

Example 3

Input
s = "ccbbaa"
Output
"abacbc"
Why
Any arrangement with no equal neighbours is accepted, for example "cbcaba" too.

Constraints

  • 1 <= s.length <= 10^4
  • s contains only lowercase English letters.

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 16 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Greedy (most frequent allowed letter)O(26 · n)O(1)
Optimal (fill even slots, then odd slots)O(n)O(n)

1Greedy (most frequent allowed letter)

TimeO(26 · n)Each of the n positions scans the 26 counts once.
SpaceO(1)A fixed array of 26 counts besides the output.

Build the answer one character at a time. At each step choose the letter with the largest remaining count that differs from the last letter placed. Spending the most frequent letter early keeps it from piling up at the end. If no letter is allowed, the task is impossible.

  1. Count every letter.
  2. Repeat n times: scan the 26 counts and pick the letter with the highest count that is not the previous letter.
  3. If no letter can be picked, return the empty string.
  4. Append it, decrease its count and remember it as the previous letter.
class Solution {
    public String reorganizeString(String s) {
        int[] count = new int[26];
        for (char c : s.toCharArray()) count[c - 'a']++;
        StringBuilder sb = new StringBuilder();
        int prev = -1;
        for (int step = 0; step < s.length(); step++) {
            int best = -1;
            for (int c = 0; c < 26; c++) {
                if (c != prev && count[c] > 0 && (best == -1 || count[c] > count[best])) best = c;
            }
            if (best == -1) return "";
            sb.append((char) ('a' + best));
            count[best]--;
            prev = best;
        }
        return sb.toString();
    }
}

2Optimal (fill even slots, then odd slots)

TimeO(n)One counting pass and one pass to place every character.
SpaceO(n)The output character array; the counts are fixed size.

If the most frequent letter appears more than (n + 1) / 2 times, there are not enough other letters to separate its copies, so the answer is empty. Otherwise write that letter on indices 0, 2, 4, ... and then keep writing every other letter into the next free even index, wrapping to index 1, 3, 5, ... when the even slots run out. Copies of the same letter always land two apart, so no neighbours match.

  1. Count the letters and find the most frequent one, top.
  2. If count[top] > (n + 1) / 2, return the empty string.
  3. Set idx = 0. Write top count[top] times at idx, moving idx by 2 each time.
  4. For every other letter, write each copy at idx; when idx >= n, jump to idx = 1. Move idx by 2 after each write.
class Solution {
    public String reorganizeString(String s) {
        int n = s.length();
        int[] count = new int[26];
        for (char c : s.toCharArray()) count[c - 'a']++;
        int top = 0;
        for (int c = 1; c < 26; c++) if (count[c] > count[top]) top = c;
        if (count[top] > (n + 1) / 2) return "";
        char[] res = new char[n];
        int idx = 0;
        while (count[top] > 0) {
            res[idx] = (char) ('a' + top);
            idx += 2;
            count[top]--;
        }
        for (int c = 0; c < 26; c++) {
            while (count[c] > 0) {
                if (idx >= n) idx = 1;
                res[idx] = (char) ('a' + c);
                idx += 2;
                count[c]--;
            }
        }
        return new String(res);
    }
}

Edge cases to test

  • A single character: it is already valid
  • One letter appears exactly (n + 1) / 2 times: it must sit on every even index
  • One letter appears more than (n + 1) / 2 times: return the empty string
  • All letters equal with length 2 or more

Hints

Hint 1

When is it impossible? Think about the most frequent letter and how many gaps the others can fill.

Hint 2

Building left to right, which letter is the safest to place next?

Hint 3

Place the most frequent letter on indices 0, 2, 4, ... first, then fill the remaining slots with everything else.

FAQ

What is the best time complexity for Reorganize String?

Optimal (fill even slots, then odd slots) runs in O(n) time and O(n) extra space. One counting pass and one pass to place every character.

Which pattern does Reorganize String use?

It is a arrays & hashing problem that uses the greedy pattern. Other problems with the same pattern: Integer to Roman, Jump Game II, Jump Game.

Is there a brute force solution for Reorganize String?

Yes. Greedy (most frequent allowed letter) takes O(26 · n) time and O(1) space. Build the answer one character at a time.

Which edge cases should I test for Reorganize String?

A single character: it is already valid; One letter appears exactly (n + 1) / 2 times: it must sit on every even index; One letter appears more than (n + 1) / 2 times: return the empty string; All letters equal with length 2 or more.