Reorganize String Solutions & Complexity

1. Define the problem

Reorganize String

Given a string s, rearrange its letters so that no two neighbouring letters are the same . Return any arrangement that works, or return the empty string "" when no arrangement is possible. Count how often each letter appears, then keep taking the two letters with the highest counts left and writing them side by side. Two different letters can never clash, and always spending the most common letter first stops it from piling up at the end. A max-heap keyed on the counts hands you those two letters each round. It is impossible exactly when one letter appears more than half the time, rounded up, because that letter would have to sit next to itself somewhere.

Constraints

1 ≤ s.length ≤ 500
s is made of lowercase English letters only

Example

Inputs = "vvvlo"

Output"vlvov"

Explanation The letter v appears 3 times out of 5, which is the most that can still work. Writing v, then l, then v, then o, then v keeps every pair of neighbours different. "vovlv" would also be accepted by the problem, but this solution returns "vlvov".

2. Know the words first

In plain terms

Heap: A container that always knows its best item, where best means smallest or largest depending on how you set it up. Adding an item or taking the best item out costs about log n steps, and you never have to sort the whole collection.
Backing array: A heap is stored as one plain list. The item at position i keeps its parent at position (i - 1) / 2 rounded down, and its two children at positions 2i + 1 and 2i + 2. That is why every picture below is a row of numbered boxes.
Max-heap: A heap whose best item is the largest one. Here each item is a pair of letter and count, and the heap compares the counts.
Tie-break: A second rule used when two items compare equal on the first rule. This solution breaks ties on count by preferring the alphabetically smaller letter, which makes the output predictable.
Any valid answer: More than one arrangement can be correct. The tests here expect the exact arrangement this particular solution produces.

3. Visualize the solution

The row of boxes is the backing array of the max-heap for s = "vvvlo", each box holding a letter and its count

0v:3

1l:1

2o:1

Statuscount

Count the letters and push each letter with its count into the max-heap.

What happens in this step

s = "vvvlo"
counts: v appears 3 times, l once, o once
backing array = [v:3, l:1, o:1]
out = ""

Check first: 3 is not more than (5 + 1) / 2 = 3, so an answer exists.

Step 1 of 5

Steps to visualize

Each box is one slot of the list that stores the heap. Slot 0 holds the letter with the highest count left.
A slot showing — is unused, because a letter has been used up.
Each round pops twice, writes both letters to the output, and pushes each letter back with its count reduced by one, unless it has run out.
When one letter is left over at the end it goes on the end of the string, which is safe because it can never be the letter that was just written.

4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

The row of boxes is the backing array of the max-heap for s = "vvvlo", each box holding a letter and its count

0v:3

1l:1

2o:1

Statuscount

Count the letters and push each letter with its count into the max-heap.

What happens in this step

s = "vvvlo"
counts: v appears 3 times, l once, o once
backing array = [v:3, l:1, o:1]
out = ""

Check first: 3 is not more than (5 + 1) / 2 = 3, so an answer exists.

Step 1 of 5

5. Solution

Solution

solution.tsTypeScript

function reorganizeString(s) {
  const counts = new Map();

  for (const letter of s) {
    counts.set(letter, (counts.get(letter) || 0) + 1);
  }

  const heap = new Heap((a, b) => b[1] - a[1] || (a[0] < b[0] ? -1 : 1));

  for (const [letter, count] of counts) {
    if (count > (s.length + 1) / 2) return '';
    heap.push([letter, count]);
  }

  const out = [];

  while (heap.size() > 1) {
    const first = heap.pop();
    const second = heap.pop();
    out.push(first[0], second[0]);
    if (first[1] > 1) heap.push([first[0], first[1] - 1]);
    if (second[1] > 1) heap.push([second[0], second[1] - 1]);
  }

  if (heap.size() === 1) out.push(heap.pop()[0]);

  return out.join('');
}

class Heap {
  constructor(compare) {
    this.items = [];
    this.compare = compare;
  }

  size() {
    return this.items.length;
  }

  peek() {
    return this.items[0];
  }

  push(value) {
    this.items.push(value);
    let child = this.items.length - 1;

    while (child > 0) {
      const parent = (child - 1) >> 1;
      if (this.compare(this.items[child], this.items[parent]) >= 0) break;
      const swap = this.items[child];
      this.items[child] = this.items[parent];
      this.items[parent] = swap;
      child = parent;
    }
  }

  pop() {
    const top = this.items[0];
    const last = this.items.pop();

    if (this.items.length > 0) {
      this.items[0] = last;
      let parent = 0;

      while (true) {
        const left = parent * 2 + 1;
        const right = parent * 2 + 2;
        let best = parent;

        if (left < this.items.length && this.compare(this.items[left], this.items[best]) < 0) best = left;
        if (right < this.items.length && this.compare(this.items[right], this.items[best]) < 0) best = right;
        if (best === parent) break;

        const swap = this.items[parent];
        this.items[parent] = this.items[best];
        this.items[best] = swap;
        parent = best;
      }
    }

    return top;
  }
}

Time: O(n log k) for a string of length n with k different letters
Space: O(n)

6. Test cases

Test cases

Input	Expected	Covers
`s = "vvvlo"`	`"vlvov"`	example from the docstring
`s = "aaab"`	`""`	one letter appears too often, so no arrangement works
`s = "a"`	`"a"`	smallest possible input
`s = "aab"`	`"aba"`	a leftover letter is added at the end
`s = "aabb"`	`"abab"`	two letters with equal counts, resolved by the tie-break
`s = "aaabbb"`	`"ababab"`	a larger input where every round pops a full pair

Reorganize String