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 java.util.PriorityQueue;
2import java.util.HashMap;
3
4public class ReorganizeString {
5 public String reorganizeString(String s) {
6 HashMap<Character, Integer> frequencyMap = new HashMap<>();
7 for (char c : s.toCharArray()) {
8 frequencyMap.put(c, frequencyMap.getOrDefault(c, 0) + 1);
9 }
10
11 PriorityQueue<Character> maxHeap = new PriorityQueue<>((a, b) -> frequencyMap.get(b) - frequencyMap.get(a));
12 maxHeap.addAll(frequencyMap.keySet());
13
14 StringBuilder result = new StringBuilder();
15 while (maxHeap.size() > 1) {
16 char first = maxHeap.remove();
17 char second = maxHeap.remove();
18 result.append(first);
19 result.append(second);
20 frequencyMap.put(first, frequencyMap.get(first) - 1);
21 frequencyMap.put(second, frequencyMap.get(second) - 1);
22
23 if (frequencyMap.get(first) > 0) maxHeap.add(first);
24 if (frequencyMap.get(second) > 0) maxHeap.add(second);
25 }
26
27 if (!maxHeap.isEmpty()) {
28 char last = maxHeap.remove();
29 if (frequencyMap.get(last) > 1) return "";
30 result.append(last);
31 }
32
33 return result.toString();
34 }
35}This Java solution uses a max heap to always choose the most frequent character available. We insert characters alternately and handle the case where we may have an odd leftover character at the end.
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.