Q63 Reorganize String - LeetCode
Sat Feb 04 2023 07:21:20 GMT+0000 (Coordinated Universal Time)
Saved by
@Ayush_dabas07
class Solution {
//make a pair class to store char,frequency
class pair implements Comparable<pair>{
char ch ;
int freq;
pair(char ch , int freq){
this.ch = ch;
this.freq = freq;
}
public int compareTo(pair o ){ //descending order
return o.freq - this.freq;
}
}
public String reorganizeString(String s) {
//make a maxheap to get value based on maximum frequency
Queue<pair> maxheap = new PriorityQueue<>();
//create and store frequency
HashMap<Character,Integer> map = new HashMap<>();
for(char ch : s.toCharArray())
map.put(ch ,map.getOrDefault(ch,0)+1);
//adding character,frequency to max heap
for(char key : map.keySet()){
pair p = new pair(key , map.get(key));
maxheap.add(p);
}
StringBuilder ans = new StringBuilder();
pair block = maxheap.remove();
//adding first letter in our string
ans.append(block.ch);
block.freq = block.freq - 1;
while(maxheap.size()!=0){
pair temp = maxheap.remove();
ans.append(temp.ch);
temp.freq = temp.freq-1;
//check if frequency has got to zero
if(block.freq != 0)
maxheap.add(block);
block = temp;
}
//if block element still has any frequency ,no string exists
if(block.freq > 0 )
return "";
return ans.toString();
}
}
content_copyCOPY
https://leetcode.com/problems/reorganize-string/
Comments