-
Notifications
You must be signed in to change notification settings - Fork 1
/
ReorganizeString.java
80 lines (68 loc) · 2.22 KB
/
ReorganizeString.java
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
package com.leetcode;
import java.util.HashMap;
import java.util.PriorityQueue;
//adjacent characters are not the same
public class ReorganizeString {
//https://leetcode.com/problems/reorganize-string/
/**
Example 1:
Input: s = "aab"
Output: "aba"
Example 2:
Input: s = "aaab"
Output: ""
**/
class Solution {
public String reorganizeString(String S) {
String result = "";
HashMap<Character,Integer> map = new HashMap<>();
for(char ch : S.toCharArray()){
map.put(ch,map.getOrDefault(ch,0)+1);
}
PriorityQueue<Node> maxHeap = new PriorityQueue<>((a, b)->(b.count-a.count));
for(char ch : map.keySet()){
maxHeap.offer(new Node(ch,map.get(ch)));
}
char prev = ' ';
while(maxHeap.size() >= 2){
Node node1 = maxHeap.poll();
Node node2 = maxHeap.poll();
char ch1 = node1.ch;
char ch2 = node2.ch;
if(ch1 == ch2) return "";//break
result += ch1 + "" +ch2;
prev = ch2;
node1.count = node1.count -1;
node2.count = node2.count -1;
if(node1.count > 0){
maxHeap.offer(node1);
}
if(node2.count > 0){
maxHeap.offer(node2);
}
}
if(maxHeap.size() > 0){
Node node = maxHeap.poll();
char ch = node.ch;
int count = node.count;
if(ch == prev || count != 1) return "";//break
result = result + ch;
}
return result;
}
}
class Node{
char ch;
int count;
public Node(char ch , int count){
this.ch = ch;
this.count = count;
}
}
}
/*
Note : how its different from https://leetcode.com/problems/task-scheduler/
1. input aaabc is accepted as abaca . // connot go level by level on unique character
2. End condition need all character completed . Equal length optput
3. Compare in pair if possible , In case on no pair like aaa -> a:3 return ""
*/