767. Reorganise Substring

Problem Statement

Pattern:

---

Solution

public String reorganizeString(String s) {
	PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> b[1] - a[1]);
	int[] freq = new int[26];
	
	// get char freqs
	for(char ch : s.toCharArray()) 
		if(freq[ch-'a'] + 1 > (s.length() + 1) / 2) return "";
		else freq[ch-'a']++;
	
	// insert into pq
	for(int i = 0 ; i < 26 ; i++) 
		if (freq[i] > 0) pq.add(new int[]{i + 'a', freq[i]});
	
	
	// generate string
	StringBuilder sb = new StringBuilder();
	while(!pq.isEmpty()) {
		// get highest freq char
		int[] first = pq.poll();
		
		// if same as last
		if(sb.isEmpty() || sb.charAt(sb.length()-1) != (char) first[0]) {
			sb.append((char) first[0]);
			if(--first[1] > 0) pq.add(first);
		}
		
		// if different from last
		else {
			int[] second = pq.poll();
			sb.append((char) second[0]);
			if(--second[1] > 0) pq.add(second);
			pq.add(first);
		}
	}
	
	return sb.toString();
}
 

TC : $O(nlog(26))$ SC : $O(1)$

Notes

• if any character’s freq > (size of the string + 1) / 2, the rearranging the string is impossible
• else, you can follow greedy approach, to alternate between most frequent and second most frequent characters in the string