3. 重複しない文字を含まない最長部分文字列

文字列 s が与えられた場合、重複しない文字を含む最長の部分文字列の長さを見つけてください。

例 1:

<strong>入力:</strong> s = "abcabcbb"
<strong>出力:</strong> 3
<strong>説明:</strong> 重複しない文字を含む最長部分文字列は "abc" であるため、その長さは 3 です。

例 2:

<strong>入力:</strong> s = "bbbbb"
<strong>出力:</strong> 1
<strong>説明:</strong> 重複しない文字を含む最長部分文字列は "b" であるため、その長さは 1 です。

例 3:

<strong>入力:</strong> s = "pwwkew"
<strong>出力:</strong> 3
<strong>説明:</strong> 重複しない文字を含む最長部分文字列は "wke" であるため、その長さは 3 です。
    なお、答えは<strong>部分文字列</strong>の長さでなければならず、"pwke" は<em>部分列</em>であり、部分文字列ではありません。

制約:

• 0 <= s.length <= 5 * 10^4
• s は英文字、数字、記号、および空白で構成されます

解法：

1. スライディングウィンドウ法：

• 2つのポインタ left と right を使用して、現在のウィンドウの左右境界を表します。
• 初期状態では両方のポインタが文字列の先頭を指し、右ポインタを動かしてウィンドウを拡張します。

2. 文字の格納：

• 現在のウィンドウ内の文字を格納する HashSet を使用して、文字の重複を防ぎます。

3. ウィンドウの拡張と縮小：

• 右ポインタが指す文字がセットに含まれていない場合、その文字をセットに追加し、右ポインタを右に移動します。
• 重複文字が見つかった場合（セットにすでに存在する文字）、左ポインタを右に移動し、対応する文字をセットから削除してウィンドウを縮小します。これをウィンドウ内に重複がなくなるまで繰り返します。

4. 最大長の更新：

• 右ポインタが動くたびに、重複しない部分文字列の最大長 maxLength を更新します。値は Math.max(maxLength, right - left) です。

5. 結果の返却：

• 最終的に maxLength を返し、重複しない最長部分文字列の長さを示します。

この方法はスライディングウィンドウとハッシュセットを組み合わせることで、線形時間（O(n)、nは文字列の長さ）で問題を解決します。

class LongestSubstringSolution {
    /**
     * 指定された文字列sの中で、重複しない文字を含む最長部分文字列の長さを計算します。
     * @param s 入力文字列
     * @return 重複しない文字を含む最長部分文字列の長さ
     */
    public int findMaxLength(String s) {
        int windowEnd = 0; // ウィンドウの右端を示すポインタ
        int strLength = s.length(); // 文字列sの長さ
        int maxLength = 0; // 重複しない最長部分文字列の長さ
        Set<Character> charSet = new HashSet<>(); // ウィンドウ内の文字を格納するセット
        
        for (int windowStart = 0; windowStart < strLength; windowStart++) {
            if (windowStart != 0) {
                charSet.remove(s.charAt(windowStart - 1)); // ウィンドウを縮小
            }
            while (windowEnd < strLength && !charSet.contains(s.charAt(windowEnd))) {
                charSet.add(s.charAt(windowEnd)); // ウィンドウを拡大
                windowEnd++;
            }
            maxLength = Math.max(maxLength, windowEnd - windowStart); // 最大長を更新
        }
        return maxLength; // 結果を返す
    }
}