📌Problem

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

Example 1:

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

Example 2:

Input: s = "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.

Example 3:

Input: s = "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3.
Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.

Example 4:

Input: s = ""
Output: 0

Constraints:

• 0 <= s.length <= $5 * 10^4$
• s consists of English letters, digits, symbols and spaces.

leetcode 에서 풀기

---

📝Solution

✏️ Brute force

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        
        sub_str_list=[]
        ret=0
        for cursor in range(len(s)):
            count_dict={s[cursor]:1} # { character : count }
            for move in range(cursor+1,len(s)):
                if count_dict.get(s[move],False): # Duplicated character
                    sub_str_list.append(''.join(count_dict.keys()))
                    break
                else:
                    count_dict[s[move]]=1
                    
            sub_str_list.append(''.join(count_dict.keys()))
        
        
        #Find the longest substring
        if len(sub_str_list) !=0: 
            ret=len(max(sub_str_list,key=lambda x: len(x)))
        
        return ret        
                

• Time complexity : $O(N^2)$

✏️ Sliding window

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        ans = 0
        left_cursor = 0
        used = {}
        
        for right_cursor, char in enumerate(s):
            if char in used and left_cursor <= used[char]: #Duplicated character
                left_cursor = used[char] + 1
            else:
                ans = max(ans, right_cursor - left_cursor + 1)
            used[char] = right_cursor
            
        return ans

• Time complexity : $O(N)$

• 

• $S_{ij}$ (Substring from index i to j) 에서 K 번째에 중복된 문자가 존재한다면, $S_{k+1}$ 부터 중복된 문자를 찾는 과정을 반복한다.