C#で重複文字を含まない最長部分文字列の長さを求める方法【スライディングウィンドウ解説】

与えられた文字列の中から、同じ文字が2回以上現れない最も長い部分文字列の長さを求める問題は、コーディング面接でも頻出の定番アルゴリズム課題です。この記事では、C#を使って「スライディングウィンドウ（Sliding Window）」というテクニックで効率的に解く方法を、具体例と実装コード付きでわかりやすく解説します。

スライディングウィンドウ技法とは

スライディングウィンドウでは、i と j という2つのポインタを使用します。最初は両方のポインタが文字列の先頭にある同じ文字を指しています。文字列を走査しながら、以下のルールで処理を進めます。

• 現在注目している文字 s[j] がリストに存在しない場合：その文字をリストに追加し、右側のポインタ j を1つ進めます。
• 現在注目している文字 s[j] がリストにすでに存在する場合（重複）：左側のポインタ i が指す文字をリストから削除し、i を1つ進めます。
• 処理の途中で、リスト内の文字数（＝現在のウィンドウの長さ）が最大値 max を更新できるかどうかを常に判定します。

こうすることで、ウィンドウ内には常に「重複のない文字列」だけが保持され、全パターンを総当たりせずとも答えを導き出せます。

具体例

例1

入力 − s = "abcabcbb"

出力 − 3

説明 − 答えは "abc" で、その長さは 3 です。

例2

入力 − s = "bbbbb"

出力 − 1

説明 − 答えは "b" で、その長さは 1 です。

アルゴリズムの流れ（s = "abcabcbb" の場合）

1. 'a'、'b'、'c' を順にリストへ追加 → ウィンドウは "abc"（長さ3）となり、max = 3。
2. 次の 'a' は重複なので、左端の 'a' を削除して i を進める → ウィンドウは "bc"。
3. 'a' を追加 → ウィンドウは "bca"（長さ3）。以降も同様に重複が見つかるたびに左端から削除します。
4. 文字列の末尾まで走査し終えた時点の max = 3 が答えになります。

C#での実装例

using System;
using System.Collections.Generic;

public class Arrays {
   public int LongestSubstringWithNoRepeatingCharacters(string s) {
      List<char> c = new List<char>();
      int iPointer = 0;
      int jPointer = 0;
      int max = 0;

      while (jPointer < s.Length) {
         if (c.Contains(s[jPointer])) {
            // 重複が見つかった場合：左端の文字を削除して i を進める
            c.Remove(s[iPointer]);
            iPointer++;
         } else {
            // 重複がない場合：文字を追加してから最大値を更新
            c.Add(s[jPointer]);
            max = Math.Max(c.Count(), max);
            jPointer++;
         }
      }
      return max;
   }
}

class Program {
   static void Main(string[] args) {
      Arrays arr = new Arrays();
      int res = arr.LongestSubstringWithNoRepeatingCharacters("abcabcbb");
      Console.WriteLine(res);
   }
}

実行結果

3

計算量について

時間計算量 − O(N)：左右のポインタ i と j はそれぞれ文字列の長さ N の範囲で一度しか進まないため、全体の処理は文字数に比例します。

空間計算量 − O(N)：最悪ケース（すべての文字が異なる場合）では、リストに文字列全体が格納される可能性があります。

なお、List<char> の Contains は線形探索のため厳密には O(N²) になりますが、HashSet<char> を使えば各判定を O(1) にでき、より高速化できます。面接ではこの改善点にも触れられると好印象です。