Log inSign up
mediumleetcodeNot Started

Reorganize String

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Strings
Solve on leetcode
Lesson

Problem Statement

Given a string s, rearrange the characters of s so that any two adjacent characters are not the same.

Return *any possible rearrangement of* s *or return* "" *if not possible*.

Example 1 · Example:

Input: s = "aab"
Output: "aba"
Explanation: Characters are rearranged so no two adjacent letters are equal.

Example 2 · Example:

Input: s = "aaab"
Output: ""
Explanation: Impossible to reorganize since a occurs 3 times in a string of length 4 (3 > (4+1)/2 = 2).

Constraints:

  • 1 <= s.length <= 500
  • s consists of lowercase English letters.

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Apply the Pigeonhole Principle to detect impossible arrangements in O(N).
  • Implement strided even-odd array filling.
  • Solve adjacency constraints using Max Heaps and Frequency Counting.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Rearranging sequences so that no two adjacent elements are identical.
  • Task scheduler / cooling interval arrangements.

Algorithmic Decision Tree:

  • Pigeonhole Feasibility Verification
  • Strided Array Filling
  • Max Heap Greedy Selection

Connected Patterns:

Task SchedulerRearrange String k Distance ApartDistant Barcodes

1. Max Heap Greedy Pairwise Selection

Intuition

Count character frequencies. Push all (count, char) pairs into a max-heap. While heap has >= 2 elements, pop top two characters (cnt1, ch1) and (cnt2, ch2). Append both to the result string, decrement counts, and push back if counts > 0. If 1 element remains: if count == 1, append it; if count > 1, return "".

When to apply: When modeling general distance constraints (e.g. k distance apart).

Algorithm

  1. Count frequencies in map.
  2. Push all (count, char) into max-heap pq.
  3. Initialize res = "".
  4. While pq.size() >= 2:
  5. Pop (c1, ch1) and (c2, ch2).
  6. res += ch1; res += ch2.
  7. If c1 > 1: pq.push(c1 - 1, ch1).
  8. If c2 > 1: pq.push(c2 - 1, ch2).
  9. If pq.size() == 1:
  10. pair = pq.pop()
  11. If pair.count > 1: return "".
  12. res += pair.char.
  13. Return res.

Max Heap Greedy Pairwise Selection

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [a, a, b]
Current operationSTEP 1 OF 6
Observation: Count character frequencies: 'a' has count 2, 'b' has count 1
Visual state
Values and pointers at this exact step
array
Array Buffer RepresentationParent i → Left 2i+1, Right 2i+2
S
a
a
b
0
↑ FREQ: {a: 2, b: 1}
1
2
Binary Heap Tree Topology
a#0
a#1
b#2
Variables at this step
maxFreq
2
limit
2
feasible
true
heap
[["a",2],["b",1]]
Check / comparison
maxFreq = 2, N = 3. Check feasibility: maxFreq <= Math.ceil(N / 2) = 2.
Decision / next transition
2 <= 2. Valid reorganization is possible. Build max-heap: [(2, 'a'), (1, 'b')].
Why this step matters

Observation: Count character frequencies: 'a' has count 2, 'b' has count 1. String length N = 3.

Decision: Feasibility check: max(freq) <= \lceil N / 2 \rceil -> 2 <= 2. Valid reorganization exists.

Invariant: If any character frequency exceeds \lceil N / 2 \rceil, pigeonhole principle guarantees adjacent duplicates.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3#include <vector>
4#include <queue>
5#include <unordered_map>
6
7class Solution {
8public:
9 std::string reorganizeString(std::string s) {
10 std::unordered_map<char, int> counts;
11 for (char c : s) counts[c]++;
12
13 std::priority_queue<std::pair<int, char>> maxHeap;
14 for (auto& [c, count] : counts) {
15 maxHeap.push({count, c});
16 }
17
18 std::string res = "";
19 while (maxHeap.size() >= 2) {
20 auto [cnt1, ch1] = maxHeap.top(); maxHeap.pop();
21 auto [cnt2, ch2] = maxHeap.top(); maxHeap.pop();
22
23 res += ch1;
24 res += ch2;
25
26 if (cnt1 - 1 > 0) maxHeap.push({cnt1 - 1, ch1});
27 if (cnt2 - 1 > 0) maxHeap.push({cnt2 - 1, ch2});
28 }
29
30 if (!maxHeap.empty()) {
31 auto [cnt, ch] = maxHeap.top(); maxHeap.pop();
32 if (cnt > 1) return "";
33 res += ch;
34 }
35 return res;
36 }
37};
38
39int main() {
40 Solution sol;
41 std::cout << sol.reorganizeString("aab") << std::endl; // "aba"
42 std::cout << sol.reorganizeString("aaab") << std::endl; // ""
43 return 0;
44}

Time & Space Complexity

  • Time complexity: O(N log 26) = O(N) — Heap size is at most 26, so all heap operations run in O(1) constant time.
  • Space complexity: O(26) = O(1)

Why Brute Force Doesn't Scale:

Eliminates heap and sorting overhead, achieving strict O(N) time and O(1) auxiliary space.

Only uses 26 integers of stack memory.

2. Count Array with Sorted Character List

Intuition

Count frequency of each character. Sort the unique characters in descending order of frequency. If the highest frequency is greater than (n + 1) / 2, return "". Otherwise, initialize result array and fill alternating indices (0, 2, 4... then 1, 3, 5...) with characters in order of their frequencies.

When to apply: Intermediate simplification before the direct in-place array fill.

Algorithm

  1. Count character counts.
  2. Sort characters by frequency descending.
  3. If maxCount > (n + 1) / 2: return "".
  4. Initialize res array of size n and idx = 0.
  5. For each character c:
  6. While count[c] > 0:
  7. If idx >= n: idx = 1.
  8. res[idx] = c
  9. idx += 2
  10. count[c]--
  11. Return res as string.

Count Array with Sorted Character List

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [a, a, b]
Current operationSTEP 1 OF 6
Observation: Count letter frequencies
Visual state
Values and pointers at this exact step
array
S
a
a
b
0
↑ COUNT & SORT
1
2
Variables at this step
sortedChars
[["a",2],["b",1]]
res
["","",""]
Check / comparison
Counts: a:2, b:1. Sort descending by count: ['a' (2), 'b' (1)].
Decision / next transition
Allocate result array of length 3: ['', '', ''].
Why this step matters

Observation: Count letter frequencies. Sort distinct characters descending by frequency.

Decision: Sorted list: ['a': 2, 'b': 1]. Allocate target array of length 3.

Invariant: Placing the most frequent character first prevents future clustering.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3#include <vector>
4#include <algorithm>
5
6class Solution {
7public:
8 std::string reorganizeString(std::string s) {
9 int count[26] = {0};
10 int n = s.size();
11 for (char c : s) count[c - 'a']++;
12
13 std::vector<std::pair<int, char>> freq;
14 for (int i = 0; i < 26; ++i) {
15 if (count[i] > 0) freq.push_back({count[i], (char)('a' + i)});
16 }
17 std::sort(freq.rbegin(), freq.rend());
18
19 if (freq[0].first > (n + 1) / 2) return "";
20
21 std::string res(n, ' ');
22 int idx = 0;
23 for (auto& [cnt, ch] : freq) {
24 while (cnt > 0) {
25 if (idx >= n) idx = 1;
26 res[idx] = ch;
27 idx += 2;
28 cnt--;
29 }
30 }
31 return res;
32 }
33};
34
35int main() {
36 Solution sol;
37 std::cout << sol.reorganizeString("aab") << std::endl; // "aba"
38 return 0;
39}

Time & Space Complexity

  • Time complexity: O(N) — Sorting 26 characters is O(1). Filling array takes O(N).
  • Space complexity: O(N)

3. Direct Even-Odd Strided Array Fill (Optimal O(N) Time, O(1) Extra Space)

Intuition

Count frequencies in count[26] and find the character maxChar with maxCount. If maxCount > (n + 1) / 2, return "". Initialize result character array of size n and idx = 0. Fill all occurrences of maxChar at even indices 0, 2, 4.... Then iterate through all other characters from a to z, placing them at idx (advancing by 2 and wrapping idx = 1 when idx >= n). Return the string.

When to apply: The standard gold standard solution for maximum performance and zero sorting overhead.

Algorithm

  1. Count frequencies in count[26]; find maxChar and maxCount.
  2. If maxCount > (n + 1) / 2: return "".
  3. Create res array of size n.
  4. Set idx = 0.
  5. While count[maxChar] > 0:
  6. res[idx] = maxChar; idx += 2; count[maxChar]--.
  7. For each character i from 0 to 25:
  8. While count[i] > 0:
  9. If idx >= n: idx = 1.
  10. res[idx] = ('a' + i); idx += 2; count[i]--.
  11. Return res as string.

Max-Heap Interleaved Parity Filling

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [a, a, b]
Current operationSTEP 1 OF 6
Observation: Count frequencies: a: 2, b: 1
Visual state
Values and pointers at this exact step
array
Array Buffer RepresentationParent i → Left 2i+1, Right 2i+2
S
a
a
b
0
↑ Frequency check
1
2
Binary Heap Tree Topology
a#0
a#1
b#2
Variables at this step
counts
{"a":2,"b":1}
maxFreq
2
totalLen
3
maxAllowed
2
feasible
true
Why this step matters

Observation: Count frequencies: a: 2, b: 1. Maximum frequency is 2 for length 3.

Decision: maxFreq (2) <= Math.floor((3 + 1) / 2) = 2. Valid reorganization is possible.

Invariant: If any frequency exceeds (N + 1) / 2, adjacent duplicates are unavoidable.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3#include <vector>
4
5class Solution {
6public:
7 std::string reorganizeString(std::string s) {
8 int count[26] = {0};
9 int n = s.size();
10 for (char c : s) count[c - 'a']++;
11
12 int maxCount = 0, maxChar = 0;
13 for (int i = 0; i < 26; ++i) {
14 if (count[i] > maxCount) {
15 maxCount = count[i];
16 maxChar = i;
17 }
18 }
19
20 if (maxCount > (n + 1) / 2) return "";
21
22 std::string res(n, ' ');
23 int idx = 0;
24
25 // Place most frequent character first
26 while (count[maxChar] > 0) {
27 res[idx] = (char)('a' + maxChar);
28 idx += 2;
29 count[maxChar]--;
30 }
31
32 // Place remaining characters
33 for (int i = 0; i < 26; ++i) {
34 while (count[i] > 0) {
35 if (idx >= n) idx = 1;
36 res[idx] = (char)('a' + i);
37 idx += 2;
38 count[i]--;
39 }
40 }
41 return res;
42 }
43};
44
45int main() {
46 Solution sol;
47 std::cout << sol.reorganizeString("aab") << std::endl; // "aba"
48 std::cout << sol.reorganizeString("aaab") << std::endl; // ""
49 return 0;
50}

Time & Space Complexity

  • Time complexity: O(N) strictly — Single pass to count characters, and single pass to populate the result array.
  • Space complexity: O(1) auxiliary space (excluding O(N) output string)

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Max Heap Pairwise GreedyO(N log A) where A = 26O(A)Intuitive greedy simulation popping top 2 most frequent characters at each step.Heap push/pop overhead.
2.Even-Odd Index Array Fill (Optimal)OptimalO(N) strictlyO(N) for output buffer, O(1) auxiliaryDirect linear time, zero heap allocations, cleanest code.Requires sorting or finding max frequency character first.

Common Pitfalls & Crucial Edge Cases

Pitfall 1:

Placing characters at odd indices before filling the most frequent character on even indices.

Pitfall 2:

Using maxCount > n / 2 instead of maxCount > (n + 1) / 2 (which fails on odd length strings like aab).

Crucial Edge Cases to Validate:

  • Impossible arrangement (e.g. s = aaab): maxCount (3) > (4+1)/2 (2), returns "" immediately.
  • Single character string (s = a): maxCount (1) <= (1+1)/2 (1), returns a.
  • String with all distinct characters (s = abcdef): Even-odd fill places all characters without conflicts.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Start by proving the impossibility threshold (n + 1) / 2 via Pigeonhole Principle.
  2. Explain the even-odd strided array fill algorithm as the optimal O(N) solution.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why must the most frequent character be placed on even indices first before other characters?

Back to DSA Sheet