767. Reorganize String - Explanation

Description

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

You can return any possible rearrangement of s or return "" if not posssible.

Example 1:

Input: s = "axyy"

Output: "xyay"

Example 2:

Input: s = "abbccdd"

Output: "abcdbcd"

Example 3:

Input: s = "ccccd"

Output: ""

Constraints:

1 <= s.length <= 500.
s is made up of lowercase English characters.

Company Tags

Please upgrade to NeetCode Pro to view company tags.

1. Frequency Count

Intuition

To avoid adjacent duplicates, we should always place the most frequent remaining character, then the second most frequent. This greedy approach works because alternating between the two most common characters maximizes our ability to separate identical characters. If any character appears more than (n + 1) / 2, reorganization is impossible.

Algorithm

Count the frequency of each character in freq array.
If the max frequency exceeds (n + 1) / 2, return an empty string.
While building the res:
- Find the character with the highest frequency at index maxIdx and append it.
- If that character's freq[maxIdx] still has remaining count, temporarily hide it and find the next highest frequency character.
- Append the second character and restore the first character's count.
Return the res string.

class Solution:
    def reorganizeString(self, s: str) -> str:
        freq = [0] * 26
        for char in s:
            freq[ord(char) - ord('a')] += 1

        max_freq = max(freq)
        if max_freq > (len(s) + 1) // 2:
            return ""

        res = []
        while len(res) < len(s):
            maxIdx = freq.index(max(freq))
            char = chr(maxIdx + ord('a'))
            res.append(char)
            freq[maxIdx] -= 1
            if freq[maxIdx] == 0:
                continue

            tmp = freq[maxIdx]
            freq[maxIdx] = float("-inf")
            nextMaxIdx = freq.index(max(freq))
            char = chr(nextMaxIdx + ord('a'))
            res.append(char)
            freq[maxIdx] = tmp
            freq[nextMaxIdx] -= 1

        return ''.join(res)

Time & Space Complexity

Time complexity: $O(n)$
Space complexity:
- $O(1)$ extra space, since we have at most $26$ different characters.
- $O(n)$ space for the output string.

2. Frequency Count (Max-Heap)

Intuition

A maxHeap efficiently gives us the most frequent character at any time. We pop the top character, add it to res, then push it back with decremented count after processing the next character. This delay ensures we never place the same character twice in a row. If the heap is empty but we still have a prev pending character, reorganization failed.

Algorithm

Count frequencies and build a maxHeap of (count, character) pairs.
Track a prev element that was just used and cannot be immediately reused.
While the maxHeap is not empty or prev exists:
- If prev exists but the maxHeap is empty, return an empty string.
- Pop the top element cnt, append its character, and decrement cnt.
- Push prev back to the maxHeap if it exists.
- Set prev to the current element if its count is still positive.
Return the res string.

class Solution:
    def reorganizeString(self, s: str) -> str:
        count = Counter(s)
        maxHeap = [[-cnt, char] for char, cnt in count.items()]
        heapq.heapify(maxHeap)

        prev = None
        res = ""
        while maxHeap or prev:
            if prev and not maxHeap:
                return ""

            cnt, char = heapq.heappop(maxHeap)
            res += char
            cnt += 1

            if prev:
                heapq.heappush(maxHeap, prev)
                prev = None

            if cnt != 0:
                prev = [cnt, char]

        return res

Time & Space Complexity

Time complexity: $O(n)$
Space complexity:
- $O(1)$ extra space, since we have at most $26$ different characters.
- $O(n)$ space for the output string.

3. Frequency Count (Greedy)

Intuition

Instead of building the string character by character, we can place characters at alternating indices. First, fill all even indices (0, 2, 4, ...) with the most frequent character. This guarantees no two identical characters are adjacent since they are separated by at least one position. Then fill the remaining positions with other characters, wrapping to odd indices when even slots are exhausted. We use idx to track the current position and update it using idx += 2.

Algorithm

Count frequencies in freq and find the most frequent character at maxIdx.
If the max frequency exceeds (n + 1) / 2, return an empty string.
Place the most frequent character at indices 0, 2, 4, ... until exhausted.
For all remaining characters i:
- Place them at the current idx, incrementing by 2 each time.
- When the idx exceeds n, wrap to idx = 1 and continue with odd positions.
Return the res string.

class Solution:
    def reorganizeString(self, s: str) -> str:
        freq = [0] * 26
        for char in s:
            freq[ord(char) - ord('a')] += 1

        max_idx = freq.index(max(freq))
        max_freq = freq[max_idx]
        if max_freq > (len(s) + 1) // 2:
            return ""

        res = [''] * len(s)
        idx = 0
        max_char = chr(max_idx + ord('a'))

        while freq[max_idx] > 0:
            res[idx] = max_char
            idx += 2
            freq[max_idx] -= 1

        for i in range(26):
            while freq[i] > 0:
                if idx >= len(s):
                    idx = 1
                res[idx] = chr(i + ord('a'))
                idx += 2
                freq[i] -= 1

        return ''.join(res)

Time & Space Complexity

Time complexity: $O(n)$
Space complexity:
- $O(1)$ extra space, since we have at most $26$ different characters.
- $O(n)$ space for the output string.

Common Pitfalls

Incorrect Impossibility Check

The condition for impossibility is when the most frequent character appears more than (n + 1) / 2 times. Using n / 2 or forgetting the ceiling division leads to incorrect rejection of valid inputs or acceptance of impossible cases.

Placing Characters at Wrong Indices in Greedy Approach

When using the index-based greedy approach, characters must be placed at even indices first (0, 2, 4, ...) before wrapping to odd indices. Failing to reset the index to 1 after exceeding the array length results in index out-of-bounds errors or incorrect placements.

Re-inserting the Same Character into the Heap Immediately

In the heap-based approach, the just-used character must be held back for one iteration before reinsertion. Pushing it back immediately allows it to be selected again on the next pop, creating adjacent duplicates.