3. Longest Substring Without Repeating Characters

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.

Constraints:

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

• 문제 코드

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        
        if len(s)<=1:
            return len(s)
        
        newChar = ""
        maxCount = 0
        nowCount = 0
        for i in range(len(s)):
            
            if s[i] in newChar:
                for j in range(len(newChar)):
                    if newChar[j]==s[i]:
                        break
                maxCount = max(maxCount, nowCount)
                
                newChar = newChar[j+1:]+s[i]
                nowCount=  len(newChar)
            else:
                newChar+=s[i]
                nowCount+=1
                maxCount = max(maxCount, nowCount)
        return maxCount

• 문제 풀이
  - 문자열의 맨 앞에서부터 새로운 문자열에 추가하고, 이미 있는 문자면 새로운 문자열에서 해당 문자의 위치를 찾는다.
  • 문자를 찾으면 그 문자 다음부터 새로운 문자를 만든다.
  • 아니면 문자열 길이 갱신
  • worst는 문자열의 ~aa 이런경우일것 같은데, O(n^3)? 인듯