Reorganize String
To rearrange the characters of the given string s
so that no two adjacent characters are the same, we can follow these steps:
Count the Occurrences: Count the occurrences of each character in the string using a Counter.
Create a Max Heap: Put the characters into a max heap (priority queue), prioritizing by the number of occurrences.
Build the Result: Pop characters from the heap, and add them to the result string. Make sure not to put the same character adjacent to itself. If at any point this is not possible, return an empty string.
Code
|
|
Example
s = "aab"
counts = {'a': 2, 'b': 1}
max_heap = [(-2, 'a'), (-1, 'b')]
result = ["a", "b", "a"]
output = "aba"
Insights
- Efficiency: The time complexity of the algorithm is (O(n \log k)), where (n) is the length of the string
s
, and (k) is the number of distinct characters in the string. This is due to the use of a heap, which takes (O(\log k)) time for each operation. - Handling Adjacent Characters: By using a max heap, we ensure that the character with the most remaining occurrences is always considered first. By also keeping track of the previously used character, we can prevent it from being used again immediately, ensuring that no two adjacent characters are the same.
- Edge Cases: If it is not possible to arrange the characters as required, the algorithm will detect this and return an empty string. This happens when there are too many occurrences of one character to be spread out among the other characters, such as in the example “aaab”.
Define the Terms
Define the Interface Input: string Output: string
Analyze the Input and Output
a ab aa aab => size is 3 aaa => return ’’ (if the frequency exceeds a certain size, it is NOT possible)
What is the size of the given string? What should be maximum length of the most frequently occuring letter to maintain the invariant?
Example 2: “aaab” violates the invariant, return ''
“aaab” => size = 4 letter a => 3 times
output ‘_x_x_x_x’ cannot exceed 4 for size 8 (2 * 4 - 1) < 8 ‘x_x_x’ cannot exceed 4 for size 7 (2 * 4 - 1) < 7
(2 * 5) - 1 = 9 > 8 (2 * 5) - 1 = 9 > 7
If 5 it will fail for size 8 If 5 it will fail for size 7
What is the relationship to express the invariant in the code? Impossible case is when we return ’’ ???
Identify the Invariants Two characters that are adjacent to each other are not the same.
Identify the constraints S will consist of lowercase letters and have length in range [1, 500]
Search the Problem Space
Classify the Problem
- Is there any similar problem you have worked on before?
- Task Scheduler (If we make the problem abstract by removing the OS context)
Analyze the Examples
Edge Case string with just one letter in it. Return that letter.
Solve the Problem by Hand
- Interleaving the letters
Describe the Pattern
Distill the Observations to Create Insights
Brute Force Approach
Greedy Approach
- Get the frequency of all the letters
- Iterate through the highest frequency map
- Sort by descending
- Start constructing the output string
- Is it possible to solve this problem in constant space?
Somehow interleave the repeating letter by finding the right slot for that letter.
What is this approach?
- Greedy approach
Analyze Time and Space Complexity
Time: O( ) Space: O( )
Outline the Solution
- Frequency counter by scanning the string
- Check invariant to see if it is possible to construct if it is not possible, return '’
- Highest frequency letter must be used and exhausted first
Key Takeaways
0 [2, 1]
‘aab’ [‘a’, ‘a’, ‘b’]
|
|
What is the relationship between the length of the string and whether it is possible to maintain the invariant or not?
Do we need to use frequency counter to keep track of the number of times a letter is repeating?
Is it possible to solve the problem in constant space?
@param {String} s
@return {String}
def reorganize_string(s) counter = Array.new(26, 0) most_frequent = 0 ascii = 0
s.chars.each do |c| ascii = c.ord - ‘a’.ord counter[ascii] += 1
if counter[ascii] > counter[most_frequent]
most_frequent = ascii
end
end
if (2 * counter[most_frequent] - 1 > s.size) return ’’ end
What if the second most frequency prevents from forming
the string of given string? Why is this case not handled?
i = 0
while(counter[most_frequent] != 0)
s[i] = ('a'.ord + most_frequent).chr
p s
i += 2
counter[most_frequent] -= 1
end
for j in (0...26)
while counter[j] != 0
if i >= s.size
i = 1
end
s[i] = ('a'.ord + j).chr
counter[j] -= 1
i += 2
end
end
return s
end