Reorganize String
Problem Description
Question
Given a string s, rearrange the characters of s so that any two adjacent characters are not the same.
Return any possible rearrangement of s or return "" if not possible.
Example 1:
Input: s = "aab"
Output: "aba"
Example 2:
Input: s = "aaab"
Output: ""
Constraints:
- 1 <= s.length <= 500
sconsists of lowercase English letters.
Solve it on LeetCode
Approaches
1. Greedy Approach with Counting
Intuition:
The most basic approach to solve this problem is to count the frequency of each character. We place the most frequent element at even indices to maximize the chance for any subsequent character to be placed in between without repetition.
Steps:
- Count the Frequencies:
- Use an array to count occurrences of each character.
- The size of the array will be 26 if the string only contains lowercase English letters.
- Check if Reorganization is Possible:
- Find the character with the maximum count.
- Check if its frequency is more than (n+1)/2 where n is the length of the given string. If yes, it's impossible to reorganize the string.
- Fill Characters Alternately:
- Start filling the result in such a way that no two same characters are adjacent.
- Start with even positions for the maximum frequency character, then fill odd positions.
Code:
Complexity Analysis
- Time Complexity: O(n), where n is the length of the string.
- Space Complexity: O(1), because we are using constant extra space to store frequencies.
2. Priority Queue
Intuition:
The optimal way to distribute characters without adjacency is to use a max heap which allows us to always pick the character with the highest frequency available. The idea is to append characters based on their frequency in a greedy manner.
Steps:
- Count Frequencies:
- Use a frequency map to count each character.
- Use Max-Heap:
- Build a max heap (priority queue) based on frequencies of characters.
- This enables us to always extract the most frequent character efficiently.
- Construct String:
- Continuously extract the two most frequent characters and append them to the result string.
- Decrease their count and reinsert them into the heap if they still have a pending count.
- If at the end, a single character remains with positive count, return an empty string because it's not possible to reorganize.
Code:
Complexity Analysis
- Time Complexity: O(n log k), where n is the size of the input string and k is the number of distinct characters.
- Space Complexity: O(k), to store characters in the heap.