Skip to main content

Reorganize String

This question is asked by Facebook. Given a string, check if it can be modified such that no two adjacent characters are the same. If it is possible, return any string that satisfies this condition and if it is not possible return an empty string.

Example(s)​

Example 1:

Input: s = "abb"
Output: "bab"
Explanation:
Original: "abb" has adjacent 'b's
Reorganized: "bab" has no adjacent same characters

Example 2:

Input: s = "xxxy"
Output: ""
Explanation:
Character 'x' appears 3 times out of 4 total.
It's impossible to arrange so no two 'x's are adjacent.

Example 3:

Input: s = "aab"
Output: "aba"
Explanation:
Original: "aab" has adjacent 'a's
Reorganized: "aba" has no adjacent same characters

Solution​

The solution uses a greedy approach with max heap:

  1. Count frequencies: Count how many times each character appears
  2. Check possibility: If any character appears more than (n+1)/2 times, it's impossible
  3. Greedy placement: Use max heap to place most frequent characters first
  4. Avoid adjacent: Always place the second most frequent character after the most frequent

JavaScript Solution - Greedy with Heap

/**
* Reorganize string so no two adjacent characters are same
* @param {string} s - Input string
* @return {string} - Reorganized string or empty string if impossible
*/
function reorganizeString(s) {
// Count frequency of each character
const freq = new Map();
for (const char of s) {
  freq.set(char, (freq.get(char) || 0) + 1);
}

// Check if it's possible
const maxFreq = Math.max(...Array.from(freq.values()));
const n = s.length;

// If any character appears more than (n+1)/2 times, it's impossible
if (maxFreq > Math.floor((n + 1) / 2)) {
  return '';
}

// Create array of [char, count] and sort by frequency (descending)
const chars = Array.from(freq.entries())
  .map(([char, count]) => [char, count])
  .sort((a, b) => b[1] - a[1]);

// Build result using greedy approach
const result = new Array(n);
let index = 0;

// Place characters starting with most frequent
for (const [char, count] of chars) {
  for (let i = 0; i < count; i++) {
    // Place at even indices first, then odd indices
    if (index >= n) {
      index = 1; // Switch to odd indices
    }
    result[index] = char;
    index += 2;
  }
}

return result.join('');
}

// Test cases
console.log('Example 1:', reorganizeString("abb")); 
// "bab"

console.log('Example 2:', reorganizeString("xxxy")); 
// ""

console.log('Example 3:', reorganizeString("aab")); 
// "aba"

console.log('Test 4:', reorganizeString("aaab")); 
// ""
Output:
Click "Run Code" to execute the code and see the results.

Alternative Solution (Max Heap)​

Here's a version using a max heap to always get the two most frequent characters:

/**
 * Using max heap approach
 */
function reorganizeStringHeap(s) {
  // Count frequency
  const freq = new Map();
  for (const char of s) {
    freq.set(char, (freq.get(char) || 0) + 1);
  }
  
  // Check possibility
  const maxFreq = Math.max(...Array.from(freq.values()));
  if (maxFreq > Math.floor((s.length + 1) / 2)) {
    return '';
  }
  
  // Max heap (using array sorted by frequency)
  const heap = Array.from(freq.entries())
    .map(([char, count]) => ({ char, count }))
    .sort((a, b) => b.count - a.count);
  
  const result = [];
  
  while (heap.length > 0) {
    // Get most frequent character
    const first = heap.shift();
    result.push(first.char);
    first.count--;
    
    if (heap.length > 0) {
      // Get second most frequent character
      const second = heap.shift();
      result.push(second.char);
      second.count--;
      
      // Re-insert if count > 0
      if (second.count > 0) {
        insertSorted(heap, second);
      }
    }
    
    // Re-insert first if count > 0
    if (first.count > 0) {
      insertSorted(heap, first);
    }
  }
  
  return result.join('');
}

function insertSorted(heap, item) {
  let i = 0;
  while (i < heap.length && heap[i].count > item.count) {
    i++;
  }
  heap.splice(i, 0, item);
}

Complexity​

  • Time Complexity: O(n log k) - Where n is the length of the string and k is the number of unique characters. Sorting takes O(k log k), and building result takes O(n).
  • Space Complexity: O(n) - For the frequency map and result array.

Approach​

The solution uses a greedy approach with frequency sorting:

  1. Count frequencies:

    • Count how many times each character appears
    • Find the maximum frequency

  2. Check possibility:

    • If any character appears more than (n+1)/2 times, it's impossible
    • This is because we need to alternate, and one character can't dominate

  3. Greedy placement:

    • Sort characters by frequency (descending)
    • Place most frequent characters at even indices first (0, 2, 4, ...)
    • Then place remaining at odd indices (1, 3, 5, ...)
    • This ensures no two same characters are adjacent

Key Insights​

  • Impossibility check: If max frequency > (n+1)/2, impossible
  • Greedy placement: Place most frequent characters first
  • Even/odd indices: Use even indices first, then odd indices
  • Alternating pattern: This naturally avoids adjacent duplicates
  • O(n) time: After sorting, building result is O(n)

Step-by-Step Example​

Let's trace through Example 1: s = "abb"

Step 1: Count frequencies
  'a': 1
  'b': 2
  maxFreq = 2, n = 3
  Check: 2 > (3+1)/2 = 2? No, possible ✓

Step 2: Sort by frequency
  chars = [['b', 2], ['a', 1]]

Step 3: Place characters
  result = ['', '', '']
  index = 0
  
  Place 'b' (count=2):
    result[0] = 'b', index = 2
    result[2] = 'b', index = 4 (>= 3, switch to odd)
    index = 1
  
  Place 'a' (count=1):
    result[1] = 'a', index = 3 (>= 3, done)
  
  result = ['b', 'a', 'b']
  
Result: "bab"

Visual Representation​

Example 1: s = "abb"

Frequencies:
  a: 1
  b: 2

Placement strategy:
  Even indices: 0, 2
  Odd indices: 1
  
  Place 'b' (most frequent) at even indices:
    index 0: 'b'
    index 2: 'b'
  
  Place 'a' at odd indices:
    index 1: 'a'
  
  Result: "bab" ✓

Example 2: s = "xxxy"

Frequencies:
  x: 3
  y: 1
  n = 4
  
  Check: maxFreq = 3 > (4+1)/2 = 2.5? Yes ✗
  Impossible → return ""

Edge Cases​

  • All same character: Return "" (impossible)
  • Single character: Return that character
  • Two characters alternating: Works correctly
  • One character dominates: Check if frequency > (n+1)/2
  • All different characters: Any arrangement works

Important Notes​

  • Impossibility condition: maxFreq > (n+1)/2
  • Greedy placement: Most frequent at even indices first
  • Even/odd pattern: Ensures no adjacent duplicates
  • Any valid solution: Problem asks for any valid string
  • O(n) space: For frequency map and result

Why Even/Odd Indices Work​

Key insight:

  • Place most frequent characters at even indices (0, 2, 4, ...)
  • These indices are separated by at least one position
  • Then place remaining at odd indices (1, 3, 5, ...)
  • This ensures no two same characters are adjacent

Example:

Indices: 0  1  2  3  4
Even:    0     2     4  (separated)
Odd:        1     3    (separated)
  • Task Scheduler: Similar problem with cooldown
  • Rearrange String k Distance Apart: Different constraint
  • Partition Labels: Different problem
  • Non-overlapping Intervals: Different problem

Takeaways​

  • Impossibility check first: maxFreq > (n+1)/2
  • Greedy placement at even/odd indices
  • Most frequent first ensures valid arrangement
  • O(n) time after frequency counting
  • Any valid solution is acceptable