#767

Medium

auto_awesomeGreedy choice plus invariant validation

LeetCode Problem Workspace

Reorganize String

Reorganize a string so that no two adjacent characters are the same, if possible, using a greedy approach.

hash table string greedy sorting heap priority queue

Problem Statement

Given a string s, rearrange its characters such that no two adjacent characters are the same. If such an arrangement is not possible, return an empty string. This problem requires you to carefully manage the frequency of characters and place them accordingly.

For example, if s = "aab", the result should be "aba". However, for s = "aaab", it is impossible to rearrange the string to avoid adjacent characters being the same, so the output should be an empty string.

Examples

Example 1

Input: s = "aab"

Output: "aba"

Example details omitted.

Example 2

Input: s = "aaab"

Output: ""

Example details omitted.

Constraints

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

Solution Approach

Greedy Approach

Use a greedy strategy where the most frequent characters are placed first, ensuring that no two adjacent characters are the same. Track character frequencies and use a max-heap to easily access the most frequent character available for placement.

Heap (Priority Queue) Usage

A max-heap is used to always pick the character with the highest frequency, ensuring the greedy strategy is adhered to. After placing a character, reduce its count and reinsert it into the heap, while always verifying no two adjacent characters are the same.

Edge Case Handling

Handle edge cases such as strings where all characters are the same or when the length of the string exceeds the available character placements. If the rearrangement is not possible, return an empty string.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity depends on the heap operations, with each character being inserted and removed from the heap once. The space complexity depends on the size of the string and the storage required for the character frequencies, which is O(n) where n is the length of the string.

What Interviewers Usually Probe

Can the candidate effectively handle character frequencies and heap operations?
Do they understand how to balance greedy choices with validation of the invariant (no adjacent characters)?
Is the candidate able to identify edge cases where rearrangement is impossible?

Common Pitfalls or Variants

Common pitfalls

Failing to handle edge cases where no valid rearrangement is possible, such as a string with all identical characters.
Not correctly maintaining the heap, leading to inefficient access to the most frequent characters.
Misunderstanding the greedy nature of the approach, leading to incorrect placements of characters.

Follow-up variants

What if the string is already rearranged correctly? How do we optimize this?
Can we optimize space usage if the string only consists of a few distinct characters?
How would the approach change if the problem allowed for non-adjacent characters being the same?

FAQ

What is the primary strategy to solve the 'Reorganize String' problem?

The primary strategy is a greedy approach where you prioritize placing the most frequent characters first, ensuring that no adjacent characters are the same.

How does the heap (priority queue) help in this problem?

The heap allows you to efficiently access the most frequent character available and manage its placement while maintaining the greedy approach.

What happens if the string cannot be rearranged to avoid adjacent characters being the same?

If the string cannot be rearranged due to character frequency constraints, the solution should return an empty string.

What is the complexity of the 'Reorganize String' solution?

The time complexity is dependent on heap operations, and the space complexity is O(n), where n is the length of the string.

Can this solution be optimized further for space or time?

Optimizations might be possible based on the specific constraints or properties of the input string, such as if it contains a small set of distinct characters.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

class Solution:
    def reorganizeString(self, s: str) -> str:
        n = len(s)
        cnt = Counter(s)
        mx = max(cnt.values())
        if mx > (n + 1) // 2:
            return ''
        i = 0
        ans = [None] * n
        for k, v in cnt.most_common():
            while v:
                ans[i] = k
                v -= 1
                i += 2
                if i >= n:
                    i = 1
        return ''.join(ans)

Solution 2

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

class Solution:
    def reorganizeString(self, s: str) -> str:
        n = len(s)
        cnt = Counter(s)
        mx = max(cnt.values())
        if mx > (n + 1) // 2:
            return ''
        i = 0
        ans = [None] * n
        for k, v in cnt.most_common():
            while v:
                ans[i] = k
                v -= 1
                i += 2
                if i >= n:
                    i = 1
        return ''.join(ans)

Continue Practicing

#692 top k frequent words #621 task scheduler #1054 distant barcodes