LeetCode - 3. Longest Substring Without Repeating Charactersを解く

連休で家にいないといけないのは、こういうチャレンジをする分にはありがたいなと思っていたけど、
3つ続けられることで改めて実感しますね。

問題へのリンク

https://leetcode.com/problems/longest-substring-without-repeating-characters/

問題を解く前に

今回の問題文でわからない単語はなかった。

解き方を考えてみる

同じ文字が2回出てきたらだめなので、ハッシュテーブルの衝突を使うのはどうだろう。
ハッシュテーブルで文字をキーにしていってキーが衝突したらカウント終了。一番大きいカウントが正解。

解答（NG）

# @param {String} s
# @return {Integer}
def length_of_longest_substring(s)
    h = {}
    arr = s.chars
    
    max = 0
    count = 0
    arr.each do |c|
        if h[c].nil?
            h[c] = 0
            count = count + 1
        else
            h = {c => 0}
            max = count if max < count
            count = 1
        end
    end
    max = count if max < count

    return max
end

Wrong Answer	Details
Input	"dvdf"
Output	2
Expected	3

あかん、衝突は検知できても数え直しのスタート位置が取得できない。じゃあスタート位置も持っておかないといけないか、ハッシュテーブルもスタート位置から作り直し？巻き戻るのか、そんなことしたら終わらないよな・・・ うーむ1時間悩んでギブアップ。

解法を参考に

# @param {String} s
# @return {Integer}
def length_of_longest_substring(s)
    h = {}
    arr = s.chars
    
    max = 0
    start = 0
    index = 0
    arr.each do |c|
        if !h[c].nil? && h[c] >= start
            start = h[c] + 1
        end
        h[c] = index
        index = index + 1
        max = index - start if max < index - start
    end
    max = index - start if max < index - start

    return max
end

ハッシュテーブルを利用して、keyに文字、valueにindexを保持する。またsubstringのスタート位置を個別に保持する。
スタート位置はkeyの衝突時にvalueがstartより大きいか小さいかを判断してstartより大きい場合にだけ更新する。
最大値は毎回startからindex位置までを取得する。


ハッシュテーブル作り直しに気を取られて死にました。思い込みで詰まるのは自分の弱点だなあ。
それはともかくleetcodeは計算量とかもちゃんと解説しているので、これ説明できるようになったらきっと強くなれるだろうなあと思った。