SetとMapを利用したアルゴリズム

アルゴリズムの概要

このアルゴリズムは、文字列内の各文字の頻度を計算し、頻度が重複している場合に調整を行い、全ての頻度がユニーク（他と重ならない）になるようにするものです。その際、調整に必要な操作回数を最小化し、その結果を返します。

---

アルゴリズムの詳細

ステップ1: 各文字の頻度を計算

• 入力された文字列を1文字ずつ走査し、HashMapを使用して各文字の出現回数をカウントします。
• 例えば、文字列 "aaabbbcc" の場合、HashMap は次のようになります:

  {'a': 3, 'b': 3, 'c': 2}
  

ステップ2: 重複する頻度を調整

• HashSet を使用して、すでに使用された頻度（ユニークな値）を管理します。
• 各文字の頻度がすでに HashSet に存在している場合、その頻度を1ずつ減らしていきます。
  • この減少処理は、頻度が0になるか、新しい頻度がユニークになるまで続きます。
  • 調整が必要な場合、操作回数をカウントして answer に加算します。

ステップ3: 調整後の頻度を記録

• 調整後の頻度がユニークである場合、HashSet に追加します。

---

実行例

solution("aaabbbcc")

1. 頻度計算:

   {'a': 3, 'b': 3, 'c': 2}
   

2. 頻度の調整:

   • 'a' の頻度 3 → HashSet に追加: {3}
   • 'b' の頻度 3 → 重複しているため 2 に減少 → {3, 2}
   • 'c' の頻度 2 → 重複しているため 1 に減少 → {3, 2, 1}

3. 結果:
   調整回数は 2（'b' と 'c' を調整したため）。

---

時間計算量と空間計算量

• 時間計算量:
  • 文字列を1回走査するため (O(n))。
  • 各頻度調整にかかる最大回数は頻度の値（最大で (n)）に依存するため、最悪の場合 (O(n^2))。
• 空間計算量:
  • 使用されるデータ構造は HashMap と HashSet のみで、最悪でも (O(n))。

---

このアルゴリズムの特徴

1. 効率的な文字頻度計算:
   HashMap を用いることで、頻度の計算が効率的に行えます。

2. ユニークな頻度の管理:
   HashSet を使い、頻度が重複しているかどうかを簡単に確認できます。

3. 頻度の調整:
   必要最低限の調整操作を行い、結果的に効率的な解法を実現しています。

---

改良されたコード（参考）

以下のようにコードを簡略化し、読みやすく改善しました。

import java.util.*;

class Solution {
    public int solution(String s) {
        int answer = 0;
        HashMap<Character, Integer> map = new HashMap<>();
        HashSet<Integer> usedFrequencies = new HashSet<>();

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

        for (Map.Entry<Character, Integer> entry : map.entrySet()) {
            int frequency = entry.getValue();

            while (frequency > 0 && usedFrequencies.contains(frequency)) {
                frequency--;
                answer++;
            }

            if (frequency > 0) {
                usedFrequencies.add(frequency);
            }
        }

        return answer;
    }
}

---

このアルゴリズムは、文字列の頻度調整というユニークな課題に対し、効率的でわかりやすい解法を提供しています。