Sponsored
Sponsored
This approach utilizes a max heap to always place the character with the maximum frequency next, ensuring that no two adjacent characters are the same. If the character frequency is more than half of the string length, it is impossible to rearrange.
Time Complexity: O(n log k) where n is the length of the string and k is the number of unique characters. Space Complexity: O(n)
1import heapq
2from collections import Counter
3
4def reorganize_string(s: str) -> str:
5 freq = Counter(s)
6 max_heap = [(-count, char) for char, count in freq.items()]
7 heapq.heapify(max_heap)
8
9 prev_count, prev_char = 0, ''
10 result = []
11
12 while max_heap:
13 count, char = heapq.heappop(max_heap)
14 result.append(char)
15
16 if prev_count < 0:
17 heapq.heappush(max_heap, (prev_count, prev_char))
18
19 prev_count, prev_char = count + 1, char
20
21 if len(result) != len(s):
22 return ""
23 return "".join(result)In this solution, we utilize Python's heapq library to simulate a max heap by storing negative frequencies. We arrange the highest frequency characters first and reinsert them with decremented counts after placing another character, ensuring no two adjacent characters are the same.
This approach utilizes a direct counting mechanism and attempts to place characters in a greedy manner, utilizing an array to keep track of placement positions for the most frequent characters first.
Time Complexity: O(n) due to linear scanning and filling. Space Complexity: O(1) since we use a fixed-size count array.
1#include <stdio.h>
2#include <stdlib.h>
3
This C solution determines the most frequent character and places it in even indices. Other characters fill in remaining positions. If at any time the most frequent character cannot be placed, we return an empty string.