# Reorganize String ## Question ([LC.767](https://leetcode.com/problems/reorganize-string/description/)) > Given a string `s`, rearrange the characters of `s` so that no same characters are adjacent to each other. ## Examples ``` I: s = "aab" O: "aba" I: s = "aaab" O: "" no solution I: s = "aabb" O: "abab", "baba" multiple solutions ``` ## Brute Force Generate all permutations, check if one of them is a valid rearrangement. Guarantee to work in EXP time. Length really matters in this case. < 20 will kind of work. ## Code ```python from itertools import permutations def reorganize_string(self, s: str) -> str: if len(s) <= 1: return s # permutations yields next permuation in sorted order for perm in permutations(s): if self.is_not_adj(perm): return "".join(perm) return "" def is_not_adj(self, p_list) -> bool: if len(p_list) < 1: return True for i in range(len(p_list) - 1): if p_list[i] == p_list[i+1]: return False return True ``` Passed 26 / 71 Time Limit Exceeded on `s = "kkkkzrkatkwpkkkktrq"` ## A Better Approach We want to bring down the time complexity to polynomial time. One intuitive solution is to group the letters, sort by frequency, and then do an insertion sort for each letter starting from the end. For example, ``` I: "ccccbbbaa" Insertion sort "accccbbba" -> "acacccbbb" -> "bacaccbb" -> "babcaccb" -> "babcbacc" -> "cbabcbac" ``` The initial grouping and sorting by frequency guarantees an initial state that is solvable within n moves. No insertion sort operation should be wasted if starting in this initial state. If one insertion sort cannot find a valid place to insert the last element, then the input is unsolvable. The proof of correctness is not immediately apparent. We can try out a few examples to validate this approach. ``` I: "ccccbbaa" Sort "accccbba" -> "acacccbb" -> "bacacccb" -> "babcaccc" -> "cbabcacc" -> "cbcabcac" I: "ccccba" Sort "accccb" -> "bacccc" -> "cbaccc" -> "cbcacc" no valid pos to insert, unsolvable ``` The motivation of having this initial set up and inserting the last element is to maximize the number of valid positions per insertion. We'll explore that part a bit more later. ## Code ```python from collections import defaultdict def reorganize_string(self, s: str) -> str: if len(s) <= 1: return s # convert to a list of char s_list = list(s) # group and sort group_list = self.group_and_sort(s_list) # insertion sort the last element n = len(group_list) l = len(group_list) - 1 for _ in range(n, 1, -1): if self.is_not_adj(group_list): return "".join(group_list) inserted = False for i in range(0, n - 1, 1): # insert to front if i == 0 and group_list[i] != group_list[l]: last_val = group_list.pop() group_list.insert(0, last_val) inserted = True break elif group_list[i] != group_list[l] and group_list[i+1] != group_list[l]: # insert in between last_val = group_list.pop() group_list.insert(i+1, last_val) inserted = True break if not inserted: return "" return "".join(group_list) def group_and_sort(self, s_list): char_map = defaultdict(int) for char in s_list: char_map[char] += 1 group_list = [] for char in sorted(char_map, key=char_map.get, reverse=True): for i in range(char_map[char]): group_list.append(char) return group_list def is_not_adj(self, p_list) -> bool: if len(p_list) < 1: return True for i in range(len(p_list) - 1): if p_list[i] == p_list[i+1]: return False return True ``` This code is accepted with 102ms runtime. The initial grouping and sorting can be O(nlogn). The insertion sort is O(n^2). ## Heap Approach To do better than O(n^2), we have to evaluate solutions that are O(nlogn) or O(n). We can achieve O(nlogn) with heap. ## Code ```python import heapq def reorganizeString(self, s: str) -> str: if len(s) <= 1: return s # step 1 group letters letter_map = defaultdict(int) for l in s: letter_map[l] += 1 # step 2 init max heap max_heap = [] for l in letter_map: heapq.heappush(max_heap, (-letter_map[l], l)) # step 3 pop from max heap, append to result, insert back to heap result = "" while len(max_heap) > 0: first_pop = heapq.heappop(max_heap) first_count = abs(first_pop[0]) first_letter = first_pop[1] if len(result) == 0 or result[-1] != first_letter: result += first_letter if first_count > 1: first_count -= 1 heapq.heappush(max_heap, (-first_count, first_letter)) else: if len(max_heap) == 0: return "" second_pop = heapq.heappop(max_heap) second_count = abs(second_pop[0]) second_letter = second_pop[1] result += second_letter if second_count > 1: second_count -= 1 heapq.heappush(max_heap, (-second_count, second_letter)) # first group has to be pushed back too heapq.heappush(max_heap, first_pop) return result ``` Worst case O(nlogk) + O(2nlogk) which is just O(nlogk). 24ms beats 99.12%. --- # Agent Instructions: Querying This Documentation If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question. Perform an HTTP GET request on the current page URL with the `ask` query parameter: ``` GET https://zedive.gitbook.io/project-l/part-1/basic_data_structure/heap/reorganize-string.md?ask= ``` The question should be specific, self-contained, and written in natural language. The response will contain a direct answer to the question and relevant excerpts and sources from the documentation. Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.