Course4all
Join us on telegram
Home/dsa/Greedy/Reorganize String

Reorganize String

Master this topic with zero to advance depth.

Reorganize String

Rearrange string so no two adjacent characters are identical.

Visual Representation

s = "aaabcc" a: 3, b: 1, c: 2 1. Fill 'a' at 0, 2, 4 -> [a, _, a, _, a, _] 2. Fill 'c' at 1, 3 -> [a, c, a, c, a, _] 3. Fill 'b' at 5 -> [a, c, a, c, a, b]
Medium

Examples

Input: s = "aab"
Output: "aba"

Interleaving 'a' and 'b' satisfies the requirement.

Approach 1

Level I: Brute Force (All Permutations)

Intuition

Generate all possible permutations of the input string SS and check if any of them satisfy the condition that no two adjacent characters are identical.

Thought Process

  1. Use recursion to generate all N!N! permutations.
  2. For each unique permutation, check adjacency: s[i] == s[i+1].
  3. Return the first valid permutation found, or "" if none exist.
⏱ O(N!)💾 O(N)

Detailed Dry Run

s = "aab" Permutations: ["aab", "aba", "baa"]

  1. "aab": a == a (FAIL)
  2. "aba": a != b, b != a (SUCCESS). Return "aba".
java
public class Solution {
    public String reorganizeString(String s) {
        List<String> res = new ArrayList<>();
        permute(s.toCharArray(), 0, res);
        return res.isEmpty() ? "" : res.get(0);
    }
    private void permute(char[] chars, int idx, List<String> res) {
        if (!res.isEmpty()) return;
        if (idx == chars.length) {
            if (isValid(chars)) res.add(new String(chars));
            return;
        }
        Set<Character> used = new HashSet<>();
        for (int i = idx; i < chars.length; i++) {
            if (!used.add(chars[i])) continue;
            swap(chars, idx, i);
            permute(chars, idx + 1, res);
            swap(chars, idx, i);
        }
    }
    private boolean isValid(char[] s) {
        for (int i = 0; i < s.length - 1; i++) if (s[i] == s[i+1]) return false;
        return true;
    }
    private void swap(char[] c, int i, int j) { char t = c[i]; c[i] = c[j]; c[j] = t; }
}
Approach 2

Level II: Greedy with Max-Heap

Intuition

Always pick the most frequent character that is different from the last one placed. A Max-Heap allows us to fetch the highest frequency character efficiently.

Thought Process

  1. Count frequencies and push into a Max-Heap (count, char).
  2. In each step, pop the top character.
  3. Add it to the result and keep it aside (don't push back yet) because we can't use it in the very next step.
  4. Push the character from the previous step back into the heap if it still has remaining count.

Pattern: Priority Queue / Interleaving

⏱ O(N log 26) = O(N).💾 O(26) = O(1).

Detailed Dry Run

s = "aaabcc" Heap: [(a,3), (c,2), (b,1)]

  1. Pop (a,3). Res: "a". prev=(a,2)
  2. Pop (c,2). Res: "ac". Push prev (a,2). prev=(c,1)
  3. Pop (a,2). Res: "aca". Push prev (c,1). prev=(a,1) Result: "acacab"
java
public class Solution {
    public String reorganizeString(String s) {
        Map<Character, Integer> counts = new HashMap<>();
        for (char c : s.toCharArray()) counts.put(c, counts.getOrDefault(c, 0) + 1);
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> b[1] - a[1]);
        for (char c : counts.keySet()) pq.add(new int[]{c, counts.get(c)});
        
        StringBuilder sb = new StringBuilder();
        int[] prev = null;
        while (!pq.isEmpty()) {
            int[] cur = pq.poll();
            sb.append((char) cur[0]);
            if (prev != null && prev[1] > 0) pq.add(prev);
            cur[1]--;
            prev = cur;
        }
        return sb.length() == s.length() ? sb.toString() : "";
    }
}
Approach 3

Level III: Optimal Greedy (Frequency Interleaving)

Intuition

Place the most frequent character at even indices (0, 2, 4...). If it fits, we can always interleave the rest.

Thought Process

  1. Count frequencies. If any char count >(N+1)/2> (N+1)/2, impossible.
  2. Start with the most frequent char.
  3. Fill indices 0, 2, 4... then wrap to 1, 3, 5...

Pattern: Frequency-Based Positioning

⏱ O(N).💾 O(N).

Detailed Dry Run

s = "aab" Max char 'a' count = 2. Place at 0, 2. [a, _, a] Next char 'b' count = 1. Place at 1. [a, b, a]

java
public class Solution {
    public String reorganizeString(String s) {
        int[] counts = new int[26];
        for (char c : s.toCharArray()) counts[c - 'a']++;
        int max = 0, letter = 0, n = s.length();
        for (int i = 0; i < 26; i++) {
            if (counts[i] > max) { max = counts[i]; letter = i; }
        }
        if (max > (n + 1) / 2) return "";
        char[] res = new char[n];
        int idx = 0;
        while (counts[letter] > 0) {
            res[idx] = (char) (letter + 'a');
            idx += 2;
            counts[letter]--;
        }
        for (int i = 0; i < 26; i++) {
            while (counts[i] > 0) {
                if (idx >= n) idx = 1;
                res[idx] = (char) (i + 'a');
                idx += 2; counts[i]--;
            }
        }
        return String.valueOf(res);
    }
}
← Previous QuestionPatching Array
Next Question →Minimum Number of K Consecutive Bit Flips