LeetCode - Reorganize String

문제 설명

Given a string s, rearrange the characters of s so that any two adjacent characters are not the same.

Return any possible rearrangement of s or return "" if not possible.

입출력 예시

Example 1:

Input: s = "aab"
Output: "aba"

Example 2:

Input: s = "aaab"
Output: ""

제약사항

1 <= s.length <= 500
s consists of lowercase English letters.

Solution

[전략]
1. 각 알파벳의 frequency를 hashmap에 저장
2. 각 알파벳의 frequency가 높은 우선순위로 우선순위 큐를 구현
3. 우선순위큐가 empty가 될때까지, 문자열을 만들어간다.
3.1 가장 높은 우선순위 두개를 빼서
3.2 문자열에 붙이고, 각 알파벳의 frequency를 1씩 빼서 다시 우선순위 큐에 넣는다.

• 알파벳의 frequency가 0이 되면 큐에 다시 넣지 않는다.
• 큐에 알파벳이 하나만 남은 경우, frequency가 1이면 문자열에 해당 알파벳을 append하고 리턴이지만
  frequency가 2이상이면 연속된 문자가 되므로 return ""

import java.util.*;

class Solution {
   
    public String reorganizeString(String s) {
 
        HashMap<Character, Integer> alphaMap = new HashMap<>();

        for (int i = 0; i < s.length(); i++) {
            alphaMap.compute(s.charAt(i), (key, value) -> value == null ? 1 : value + 1);
        }

        PriorityQueue<Map.Entry<Character, Integer>> sq = new PriorityQueue<>(
                (a, b) -> b.getValue() - a.getValue());

        for (Map.Entry<Character, Integer> entry : alphaMap.entrySet()) {
            sq.add(entry);
        }

        StringBuilder sb = new StringBuilder();
        while (!sq.isEmpty()) {
            Map.Entry<Character, Integer> firstEntry = sq.poll();
            Map.Entry<Character, Integer> secondEntry = sq.poll();

            int firstEntryFreq = firstEntry.getValue();
            // 한가지 문자열이 남은 경우
            if (secondEntry == null) { // 한개이상 
                if (firstEntryFreq > 1) {
                    return "";
                }
                sb.append(firstEntry.getKey());
                break;
            }
            sb.append(firstEntry.getKey());
            sb.append(secondEntry.getKey());

            if (firstEntryFreq > 1) {
                firstEntry.setValue(firstEntryFreq - 1);
                sq.add(firstEntry);

                int secondEntryFreq = secondEntry.getValue();
                if (secondEntryFreq > 1) {
                    secondEntry.setValue(secondEntryFreq - 1);
                    sq.add(secondEntry);
                }
            }
        }
        return sb.toString();
    }
}