Reorganize String
Statement
Given a string s, rearrange it so that no two adjacent characters are the same. If no such rearrangement can occur, then return an empty string.
Constraints
- 1 ≤
s.length()≤ 500 sconsists of lowercase English letters
Solution
"""
production algorithm
"""
from collections import Counter
from data_structures.heap.heap import Heap
class Solution:
def reorganize_string(self, string):
"""
time complexity O(n)
space complexity O(1)
"""
length = len(string)
largest = Heap()
counter = Counter(string)
[largest.push(MaxHeapData(counter[character], character))
for character in counter]
previous, result = [], []
for _ in range(length):
if largest.empty():
break
# add current character to result
count, character = largest.pop()
result.append(character)
# add previous character back to choices
if previous:
largest.push(MaxHeapData(previous[0], previous[1]))
previous = []
# save current character as previous character
if 0 < count - 1:
previous = [count - 1, character]
if len(result) < length:
return str()
return str().join(result)
class MaxHeapData:
def __init__(self, count, character):
self.count = count
self.character = character
def __lt__(self, other):
if self.count == other.count:
return self.character < other.character
return other.count < self.count
def __iter__(self):
yield self.count
yield self.character
def __len__(self):
return 2"""
unit tests
"""
from unittest import TestCase
from algorithms.top_k_elements.reorganize_string.solution import Solution
class SolutionTestCase(TestCase):
def test_not_enough_unique_characters(self):
# Given
string = "aaaaaxyz"
solution = Solution()
# When
actual = solution.reorganize_string(string)
# Then
expected = str()
self.assertEqual(actual, expected)
def test_just_enough_unique_characters(self):
# Given
string = "aaaaawxyz"
solution = Solution()
# When
actual = solution.reorganize_string(string)
# Then
expected = "awaxayaza"
self.assertEqual(actual, expected)
def test_more_than_enough_unique_characters(self):
# Given
string = "aaaaauvwxyz"
solution = Solution()
# When
actual = solution.reorganize_string(string)
# Then
expected = "auavawaxayz"
self.assertEqual(actual, expected)Strategy
Top K Elements.
Explanation
First, count all unique characters of the input string. Then order characters by their count in a max heap. The max heap will be iterated, and the most occurrent character at the top of the max heap will be added as the next character of the result.
In more detail, for each iteration, pop the most occurrent character from the top of the heap and add that character as the next character of the result. Next, if there’s a previous character of the result, then push that character back to the heap. Finally, save the current character as the previous character. When a character is saved as the previous character, its occurrence is decremented to show the remaining number of occurrences of the character in the string.
Time Complexity
The time complexity depends on the number of characters of the string, and the number of unique characters. There will be n iterations of the heap, where n is the number of characters of the string, and the maximum size of the heap is the number of unique characters. The maximum number of unique characters is 26 since characters are lowercase English characters. Therefore, operations on the heap take constant time. Therefore, the time complexity of the algorithm is O(n).
Space Complexity
The auxiliary space complexity depends on the size of the heap which is at most 26. Therefore, the auxiliary space complexity of the algorithm is O(1).
