3. Longest Substring Without Repeating Characters

問題：Given a string s, find the length of the longest substring without repeating characters.

Input: s = "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.

文字列の中から、連続する文字列で重複がない最長の長さを求めよという問題。
チェックする文字列の最初と最後をi, jとして前探索すると、O(N^2)になってします。

以下の様な文字列があった場合、二個目のｂで重複が見つかります。そしたら、一個目のｂの次まで、重複リストから外しながら検索していき、次の文字列のスタート位置を一個目のｂの次の文字に設定します。

こうすると、N-2N計算量になります。

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        ans = 1
        n = len(s)
        temp = 1
        if n == 0 or n == 1:
            return n
        start=0
        check = set(s[0])
        for i in range(1, n):
            if s[i] in check:
                ans = max(ans, temp)
                for j in range(start, i):
                    if s[j] != s[i]:
                        check.remove(s[j])
                    else:
                        start = j + 1
                        temp = i - j
                        break
                check.add(s[i])
            elif i == n - 1:
                temp += 1
                ans = max(ans, temp)
            else:
                temp += 1
                check.add(s[i])
        return ans