Reorganize String
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^4scontains 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.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
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.
| Approach | Time | Space |
|---|---|---|
| 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)
O(26 · n)Each of the n positions scans the 26 counts once.O(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.
- Count every letter.
- Repeat n times: scan the 26 counts and pick the letter with the highest count that is not the previous letter.
- If no letter can be picked, return the empty string.
- 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();
}
}class Solution:
def reorganizeString(self, s: str) -> str:
count = [0] * 26
for ch in s:
count[ord(ch) - 97] += 1
out: List[str] = []
prev = -1
for _ in range(len(s)):
best = -1
for c in range(26):
if c != prev and count[c] > 0 and (best == -1 or count[c] > count[best]):
best = c
if best == -1:
return ""
out.append(chr(97 + best))
count[best] -= 1
prev = best
return "".join(out)class Solution {
public:
string reorganizeString(string s) {
int count[26] = {0};
for (char c : s) count[c - 'a']++;
string out;
int prev = -1;
for (size_t step = 0; step < s.size(); 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 "";
out.push_back((char) ('a' + best));
count[best]--;
prev = best;
}
return out;
}
};function reorganizeString(s) {
const count = new Array(26).fill(0);
for (const ch of s) count[ch.charCodeAt(0) - 97]++;
const out = [];
let prev = -1;
for (let step = 0; step < s.length; step++) {
let best = -1;
for (let c = 0; c < 26; c++) {
if (c !== prev && count[c] > 0 && (best === -1 || count[c] > count[best])) best = c;
}
if (best === -1) return "";
out.push(String.fromCharCode(97 + best));
count[best]--;
prev = best;
}
return out.join("");
}2Optimal (fill even slots, then odd slots)
O(n)One counting pass and one pass to place every character.O(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.
- Count the letters and find the most frequent one,
top. - If count[top] > (n + 1) / 2, return the empty string.
- Set idx = 0. Write
topcount[top] times at idx, moving idx by 2 each time. - 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);
}
}class Solution:
def reorganizeString(self, s: str) -> str:
n = len(s)
count = [0] * 26
for ch in s:
count[ord(ch) - 97] += 1
top = max(range(26), key=lambda c: count[c])
if count[top] > (n + 1) // 2:
return ""
res = [""] * n
idx = 0
while count[top] > 0:
res[idx] = chr(97 + top)
idx += 2
count[top] -= 1
for c in range(26):
while count[c] > 0:
if idx >= n:
idx = 1
res[idx] = chr(97 + c)
idx += 2
count[c] -= 1
return "".join(res)class Solution {
public:
string reorganizeString(string s) {
int n = s.size();
int count[26] = {0};
for (char c : s) 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 "";
string res(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 res;
}
};function reorganizeString(s) {
const n = s.length;
const count = new Array(26).fill(0);
for (const ch of s) count[ch.charCodeAt(0) - 97]++;
let top = 0;
for (let c = 1; c < 26; c++) if (count[c] > count[top]) top = c;
if (count[top] > Math.floor((n + 1) / 2)) return "";
const res = new Array(n);
let idx = 0;
while (count[top] > 0) {
res[idx] = String.fromCharCode(97 + top);
idx += 2;
count[top]--;
}
for (let c = 0; c < 26; c++) {
while (count[c] > 0) {
if (idx >= n) idx = 1;
res[idx] = String.fromCharCode(97 + c);
idx += 2;
count[c]--;
}
}
return res.join("");
}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.