NeetCodeのSolutionを書いていく

#

Longest Substring Without Repeating Characters

#

問題概要

#

文字列sが与えられます。文字が重複しない最も長い文字列を見つけなさい。

例

#

Input: s = “zxyzxyz” Output: 3

Input: s = “xxxx” Output: 1

制約

• 文字列長0以上1000以下
• sはプリント可能なASCII文字が含まれる可能性がある

計算時間：O(n) メモリ：O(m) nは文字列長、mはユニークな文字の数

メモ

#

まずプリント可能なASCII文字、という制約はなんなんだ？ 単純に「アルファベット+数字+記号」という感じ？あえて指定している意味がよくわからない。 アルファベットだけでも問題としては成り立つのでは？

メモリとしてユニークな文字数の数があるということは、それだけ何かを保存するということか？ まず、ブルートフォース的な方法としては、全ての文字に対して後ろ方向にユニークな文字が連続する数を数えれば良い。 ただ、それだとO(n^2)になりそう。

Sliding Windowを使うんだよな・・・ 全然わからなかったので回答を見た。 以下でできる。

• ユニークなサブ文字列となりうる文字列のポインタl,rを定義
• rを動かしながらサブ文字列を構成
• サブ文字列に重複が出たら、その文字をサブ文字列から削除
• 削除した場合は左のポインタを右に動かす
• r- 1 + 1がユニークなサブ文字列長なので、その最大値を保持
• 上記を繰り返す

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        char_set: set[str] = set()
        l = 0
        ret = 0
        for r in range(len(s)):
            while s[r] in char_set:
                char_set.remove(s[l])
                l += 1
            char_set.add(s[r])
            ret = max(ret, r - l + 1)
        return ret