【Swift】LeetCode#3: スライディングウインドウ法による解答例

解法

class Solution {
    func lengthOfLongestSubstring(_ s: String) -> Int {
        let array_s = Array(s).map { String($0) }
        var set: Set<String> = []  // 現在のウィンドウにある文字
        var left = 0               // ウィンドウの左端
        var maxLength = 0

        for right in 0..<array_s.count {
            while set.contains(array_s[right]) {
                // 重複文字があれば左端を右に動かして消す
                set.remove(array_s[left])
                left += 1
            }
            set.insert(array_s[right])
            maxLength = max(maxLength, right - left + 1)
        }

        return maxLength
    }
}

問題

問題に関しては転載禁止だと思われるのでここでは割愛します。サイトを確認してみてください。上記はスライディングウインドウ法を用いた回答となっています。

方針

1. left と right で「窓（ウィンドウ）」を作る
2. 条件を満たす間は right を伸ばす
3. 条件が崩れたら left を動かしてウィンドウを縮める
4. 最大／最小値を更新しながら進める

イメージとしては、
●◾︎⬜︎⬜︎⬜︎
●⬜︎◾︎⬜︎⬜︎
●⬜︎⬜︎◾︎⬜︎　❌ //重複を検知

●◾︎⬜︎⬜︎

●...left, ◾︎...rightみたいなイメージ

コード解説

• 文字列Sを配列に切り出す。

let array_s = Array(s).map { String($0) }

• Set<String>型の配列を宣言する。
• 文字の重複を管理するSet。

var set: Set<String> = []

• 一番左の文字, 最高記録を格納するための変数

var left = 0 
var maxLength = 0

• forループを用いて, 右の文字を全検索する

for right in 0..<array_s.count {...}

• 右の文字が変数setに入っているかを検知する

while set.contains(array_s[right]) {...}

• setの重複文字を検知したタイミングでleftを削除する
• leftを右にずらす

set.remove(array_s[left])
left += 1

• setに右の文字をinsertする

set.insert(array_s[right])

• maxLengthを更新, maxLengthとrightとleftの距離を比較して大きい方を更新する

maxLength = max(maxLength, right - left + 1)