Sliding Window アルゴリズムを利用した問題解決

LeetCode

目的

与えられた文字列において、重複する文字がない最長部分文字列の長さを求めるアルゴリズムを改善します。このためにスライディングウィンドウ手法を使用します。

初期コードの問題点

初期コードでは、重複する文字が見つかるたびにleftポインタを重複する文字が位置するインデックスの次の位置に移動させる方式で最長部分文字列を計算しています。しかし、この過程でleftポインタが非効率的に移動する可能性があります。

改善されたアルゴリズム

改善されたアルゴリズムは、重複する文字が見つかった場合、leftポインタを一度にジャンプさせて移動することで効率を向上させます。

アルゴリズムの詳細な説明

1. ポインタおよび変数の初期化:

   • leftとrightポインタをそれぞれ文字列の開始位置（0）に初期化します。
   • max変数を0に初期化して最長部分文字列の長さを保存します。
   • 各文字の最後の位置を保存するためにmapを使用します。

2. スライディングウィンドウ:

   • rightポインタが文字列の末尾に達するまでループします。
   • 現在の文字がmapに既に存在する場合、leftポインタを重複する文字の次の位置に移動させます。このためにleft = Math.max(left, map.get(currentChar) + 1)を使用します。
   • 現在の文字の位置をmapに更新します。
   • 現在のウィンドウの長さ（right - left + 1）と比較してmax値を更新します。
   • rightポインタを増加させます。

3. 結果の返却:

   • 最終的に計算されたmax値を返します。

コード

public static int lengthOfLongestSubString(String s) {
    HashMap<Character, Integer> map = new HashMap<>();
    int left = 0;
    int right = 0;
    int max = 0;

    while (right < s.length()) {
        char currentChar = s.charAt(right);
        if (map.containsKey(currentChar)) {
            // leftを現在の値とcurrentCharの最後の出現の次の位置の最大値に更新
            left = Math.max(left, map.get(currentChar) + 1);
        }
        // 現在の文字のインデックスでmapを更新
        map.put(currentChar, right);
        // 見つかった最大の長さを更新
        max = Math.max(max, right - left + 1);
        right++;
    }

    return max;
}

改善された部分

1. ポインタ移動の最適化:

   • leftポインタが重複する文字の次の位置に一度にジャンプして移動します。
   • Math.max(left, map.get(currentChar) + 1)を使用してleftポインタが非効率的に移動するのを防ぎます。

2. 効率的なメモリ管理:

   • mapを使用して各文字の最後の位置を記録し、重複する文字の検査を効率的に行います。

3. 時間計算量:

   • このアルゴリズムは文字列を一度だけ巡回するので、時間計算量はO(n)です。

この改善されたアルゴリズムは、重複する文字がない最長部分文字列の長さを効率的に計算し、スライディングウィンドウとハッシュマップを活用して性能を最適化しています。