48. Longest Substring Without Repeating Characters

読了目安約2分

Sliding Window / LeetCode 3 (Medium) — 同じ文字を含まない最長部分文字列の長さをスライディングウィンドウで求める。

この章の目次

問題

LeetCode 3. Longest Substring Without Repeating Characters（Medium / カテゴリ: Sliding Window）

文字列 s の中で、同じ文字を 2 回含まない連続した部分文字列の最長の長さを返します。 s は英字、数字、記号、空白を含むことがあり、空文字列のこともあります。

考え方

ヒント 1

区間 [left, right] を「重複なし」を保ったまま動かします。 right を 1 つ進めて重複が生じたら、重複が消えるまで left を進めます。この動かし方をスライディングウィンドウ（尺取り法）と呼びます。

ヒント 2

各文字が最後に現れた位置を辞書（Dictionary）に記録すると、left を 1 ずつではなく「重複した文字の直後」まで一気に飛ばせます。ただし記録された位置が left より前なら、その文字は今の区間に入っていないので無視します。

Swift 実装のポイント

Swift の String は整数の添字で直接アクセスできません。最初に Array(s) で [Character] に変換します。
lastIndex[c] >= left の確認を忘れると、"abba" のような入力で left が逆戻りします。
答えの更新は毎回 max(best, right - left + 1) です。空文字列ならループが回らず 0 のままになります。

模範解答

Swift
class Solution {
    func lengthOfLongestSubstring(_ s: String) -> Int {
        let chars = Array(s)
        var lastIndex: [Character: Int] = [:]
        var left = 0
        var best = 0
        for (right, c) in chars.enumerated() {
            if let i = lastIndex[c], i >= left {
                left = i + 1
            }
            lastIndex[c] = right
            best = max(best, right - left + 1)
        }
        return best
    }
}

計算量: O(n)。