-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathRearrangeString.java
More file actions
168 lines (136 loc) · 5.81 KB
/
Copy pathRearrangeString.java
File metadata and controls
168 lines (136 loc) · 5.81 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
package strings;
import java.util.*;
/* Rearrange String such that no two same characters are adjacent to each other
Java 17 solution with exceptions and edge cases
🔹 Final Comparison
Approach Time Complexity Space Complexity Best For
Max Heap (PriorityQueue) O(N log K) O(N) Best for smaller datasets
Sorting + Greedy O(N log N) O(N) Good for moderate inputs
Counting Sort (Bucket-based) O(N) O(N) Best for large inputs
🔹 Summary
• Use Approach 3 (Counting Sort + Greedy) for O(N) performance.
• Use Approach 1 (Max Heap) if a PriorityQueue-based approach is required.
• Use Approach 2 (Sorting) for a simple and structured method.
*/
public class RearrangeString {
/* Approach 3: Counting Sort (Bucket-based Greedy)
Time Complexity: O(N), Space Complexity: O(N) */
public static String rearrangeString(String s) {
int[] freq = new int[26];
for (char c : s.toCharArray()) {
freq[c - 'a']++;
}
int maxFreq = 0, maxChar = 0;
for (int i = 0; i < 26; i++) {
if (freq[i] > maxFreq) {
maxFreq = freq[i];
maxChar = i;
}
}
if (maxFreq > (s.length() + 1) / 2) return ""; // Impossible case
char[] res = new char[s.length()];
int index = 0;
while (freq[maxChar] > 0) {
res[index] = (char) (maxChar + 'a');
index += 2;
freq[maxChar]--;
}
for (int i = 0; i < 26; i++) {
while (freq[i] > 0) {
if (index >= s.length()) index = 1;
res[index] = (char) (i + 'a');
index += 2;
freq[i]--;
}
}
return new String(res);
}
public static void main(String[] args) {
List<String> testCases = List.of("aab", "aaab", "vvvlo", "aa", "abab", "aaaa", "aabbcc", "z");
for (String test : testCases) {
System.out.println("Input: " + test + " → Output: " + rearrangeString(test));
}
}
/* ✅ Approach 2: Sorting + Greedy
Time Complexity: O(N log N), Space Complexity: O(N) */
/* public static String rearrangeString(String s) {
int[] freq = new int[26];
for (char c : s.toCharArray()) {
freq[c - 'a']++;
}
int maxFreq = 0, maxChar = 0;
for (int i = 0; i < 26; i++) {
if (freq[i] > maxFreq) {
maxFreq = freq[i];
maxChar = i;
}
}
if (maxFreq > (s.length() + 1) / 2) return ""; // Impossible case
char[] res = new char[s.length()];
int index = 0;
while (freq[maxChar] > 0) {
res[index] = (char) (maxChar + 'a');
index += 2;
freq[maxChar]--;
}
for (int i = 0; i < 26; i++) {
while (freq[i] > 0) {
if (index >= s.length()) index = 1;
res[index] = (char) (i + 'a');
index += 2;
freq[i]--;
}
}
return new String(res);
}
public static void main(String[] args) {
List<String> testCases = List.of("aab", "aaab", "vvvlo", "aa", "abab", "aaaa", "aabbcc", "z");
for (String test : testCases) {
System.out.println("Input: " + test + " → Output: " + rearrangeString(test));
}
} */
/*
Edge Case Input Expected Output Explanation
All identical characters "aaaa" "" Cannot be rearranged.
Already alternating characters "abab" "abab" Already valid.
Characters with equal frequency "aabbcc" "abcabc" Multiple valid outputs.
Single character "a" "a" No adjacent characters to check.
Two different characters "ab" "ab" Already valid.
Two same characters only "aa" "" Cannot be rearranged.
Large input "aabbccddeeffgghhii...zz" "abcdefg...zabcdefg...z" Ensures O(N) complexity holds for large input.
Multiple dominant characters "vvvlo" "vlvvo" Must handle frequencies correctly.
✅ Approach 1: Max Heap (PriorityQueue)
Time Complexity: O(N log K), Space Complexity: O(N)
import java.util.*;
class RearrangeStringHeap {
public static String rearrangeString(String s) {
Map<Character, Integer> freqMap = new HashMap<>();
for (char c : s.toCharArray()) {
freqMap.put(c, freqMap.getOrDefault(c, 0) + 1);
}
PriorityQueue<Character> maxHeap = new PriorityQueue<>((a, b) -> freqMap.get(b) - freqMap.get(a));
maxHeap.addAll(freqMap.keySet());
StringBuilder result = new StringBuilder();
Queue<Character> waitQueue = new LinkedList<>();
while (!maxHeap.isEmpty()) {
char current = maxHeap.poll();
result.append(current);
freqMap.put(current, freqMap.get(current) - 1);
waitQueue.offer(current);
if (waitQueue.size() > 1) {
char ready = waitQueue.poll();
if (freqMap.get(ready) > 0) {
maxHeap.offer(ready);
}
}
}
return result.length() == s.length() ? result.toString() : "";
}
public static void main(String[] args) {
List<String> testCases = List.of("aab", "aaab", "vvvlo", "aa", "abab", "aaaa", "aabbcc", "z");
for (String test : testCases) {
System.out.println("Input: " + test + " → Output: " + rearrangeString(test));
}
}
} */
}