概要
問題
文字列
s
が与えられたとき、重複文字を含まない最長の連続部分文字列の長さを求めます。
例
s = "abcabcbb"→ 出力:3（"abc"）s = "bbbbb"→ 出力:1（"b"）s = "pwwkew"→ 出力:3（"wke"）
制約
- 入力長:
0 ≤ n ≤ 5×10⁴ - 文字種: 英字・数字・記号・空白（ASCII + 非ASCII混在可能）
- 部分文字列（substring）であり、部分列（subsequence）ではない
アルゴリズム要点
- スライディングウィンドウ: 右端を進めつつ、左端を必要に応じて前進
-
ASCII高速化:
array('I', 128)で固定・高速アクセス -
非ASCII対応:
dictでメモリ削減（BMP 65536配列を回避） - Time: O(n) — 各文字を高々1回走査
- Space: O(1) 相当（ASCII固定128、非ASCIIは出現数に比例）
ステップバイステップ解説
Python実装（LeetCode形式）
以下は、メモリ削減版の実装です。ASCIIは固定配列、非ASCIIは辞書で管理します。
from __future__ import annotations
from array import array
from typing import Dict, Final
class Solution:
"""
Longest Substring Without Repeating Characters
メモリ削減版：
- ASCII (0..127) は array('I', 128) の軽量表（未出現=0, 出現は index+1）
- 非ASCII (>=128) は dict に格納（BMP 65536表は使わない）
→ 65536 要素配列(約256KB) の確保を完全に回避してピークメモリを下げる
"""
_MAX_LEN: Final[int] = 5 * 10**4
def lengthOfLongestSubstring(self, s: str) -> int:
"""
Args:
s: 入力文字列
Returns:
重複のない最長連続部分文字列の長さ
Raises:
TypeError: s が str でない場合
ValueError: 入力長が仕様上限を超える場合
Complexity:
Time: O(n)
Space: O(1) 相当（ASCIIは固定128、非ASCIIは出現数に比例）
"""
# 入力検証
if not isinstance(s, str):
raise TypeError("Input must be a string")
n: int = len(s)
if n > self._MAX_LEN:
raise ValueError("Input length exceeds allowed maximum")
# 基底条件: 空文字列
if n == 0:
return 0
# ASCII 用（0..127）だけ固定確保：極小＆高速
last_ascii: array = array("I", [0]) * 128
# 非ASCII は dict にのみ格納（BMP 65536表は作らない）
last_other: Dict[int, int] = {}
left: int = 0 # ウィンドウ左端
best: int = 0 # 最大長
for i, ch in enumerate(s):
code: int = ord(ch)
# 分岐: ASCIIか非ASCIIか
if code < 128:
prev: int = last_ascii[code]
# 重複検出: 前回出現がウィンドウ内なら左端を前進
if prev > left:
left = prev
# 現在位置を記録（1-indexed: 0 は未出現）
last_ascii[code] = i + 1
else:
prev = last_other.get(code, 0)
if prev > left:
left = prev
last_other[code] = i + 1
# 現在ウィンドウの長さを計算
curr_len: int = i - left + 1
if curr_len > best:
best = curr_len
return best視覚的図解
アルゴリズムフローチャート
フローの説明：
1. 入力検証（型チェック・長さチェック）→ エラーなら例外を発生
2. 空文字列なら0を返して終了
3. 初期化：left=0（ウィンドウ左端）、best=0（最大長）
4. 各文字について：
・ASCII（code<128）なら配列から、非ASCIIなら辞書から前回出現位置を取得
・前回位置がウィンドウ内（prev>left）なら、leftを前進して重複を排除
・現在位置を記録し、ウィンドウ長を計算してbestを更新
5. 全文字を処理したら、bestを返して終了
計算量
時間計算量: O(n)
- 各文字を高々1回走査
- ASCIIは配列で O(1) アクセス、非ASCIIは辞書で平均 O(1)
- 左端
leftは単調増加（最大 n まで）
空間計算量: O(1) 相当
- ASCII部分:
array('I', 128)→ 512バイト固定 -
非ASCII部分:
dictは出現種類数に比例（実際は小規模）
実装比較
| 実装 | Time | Space (ASCII) | Space (非ASCII) | メモリ順位 |
|---|---|---|---|---|
| 修正前（BMP 65536配列） | O(n) | 512B | 約256KB（BMP表） | 中程度 |
| 修正後（dict） | O(n) | 512B | 出現種類数に比例 | 改善 |