3.Longest Substring Without Repeating 解答例・ポイント

問題内容

与えられた文字列内で文字が重複しない連続した文字列から最大の長さを返す

解答例

sample.py

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        n = len(s)
        maxLength = 0
        charSet = set()
        left = 0

        for right in range(n):
            if s[right] not in charSet:
                charSet.add(s[right])
                maxLength = max(maxLength, right - left + 1)
            else:
                while s[right] in charSet:
                    charSet.remove(s[left])
                    left += 1
                charSet.add(s[right])

        return maxLength    

ポイント

• 既出の文字を集合として保持する
• ループしていく過程で既出文字が現れた際に、集合から特定の既出文字がなくなるまで左端のポインタを動かす
• この処理によって重複していない文字についても集合から削除してしまうが、この問題では連続した文字列の長さについて問われているため大丈夫