Leetcode 767. Reorganize String

アプローチ

• MaxHeap

class Solution {
    public String reorganizeString(String s) {
        // 各Charの回数をもつHashMap
        HashMap<Character, Integer> hashMap = new HashMap<>();

        
        PriorityQueue<Character> maxHeap = new PriorityQueue<>((a, b) -> hashMap.get(b) - hashMap.get(a));

        for (char c : s.toCharArray()) {
            hashMap.put(c, hashMap.getOrDefault(c, 0) + 1);
        }

        for (char c : hashMap.keySet()) {
            maxHeap.offer(c);
        }

        // 結果の保存するために宣言
        char[] result = new char[s.length()];
        int resultIndex = 0;

        char maeNoChar = 0;

        while (!maxHeap.isEmpty()) {
            char nowCh = maxHeap.poll();
            int nowChCount = hashMap.get(nowCh) - 1;
            hashMap.put(nowCh, nowChCount);

            result[resultIndex++] = nowCh;

            // 前のCharに保存しなかった場合、MaxHeapに値が入ってこない
            // maxHeapの長さが0になればWhile文が終了になる
            if (maeNoChar > 0) {
                maxHeap.add(maeNoChar);
            }

            if (nowChCount > 0) {
                // 現在持ってきたCharの残っている数があれば、前のCharに保存する
                maeNoChar = nowCh;
            } else {
                // 現在持ってきたCharの残っている数がなければ、前のCharに保存しない
                maeNoChar = 0;
            }
        }

        // 前回の Charが残っている状態でWhile文が終了になるので、MaeNoCharが0でなはい
        if (maeNoChar != 0) {
            // 条件達成してないので空文字を返す
            return "";
        }

        // 条件達成しているのでで文字を返す
        return new String(result);
    }
}

動画を参考しました