3. Longest Substring Without Repeating Characters.md

3. Longest Substring Without Repeating Characters[Medium]

---

출처: https://leetcode.com/problems/longest-substring-without-repeating-characters/

• 문제

  3. Longest Substring Without Repeating Characters
  Medium
  
  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 * 104
  s consists of English letters, digits, symbols and spaces.

• 풀이

  첫번째 풀이 - Time Limit Exceeded 남..

  class Solution:
      def lengthOfLongestSubstring(self, s: str) -> int:
          leng = len(s)
          if leng == 1:
              return 1
          if leng == len(set(s)):
              return leng
          for i in range(leng, 0, -1):
              for j in range(0, leng - i + 1):
                  if len(set(s[j:j+i])) == i:
                      return i
          return 0

  이유는 모든 문자열마다 set을 해서 그런거같다. 빠를줄 알았는데 아니구나.

  Success

  class Solution:
      def lengthOfLongestSubstring(self, s: str) -> int:
          max_len = 0
          if len(set(s)) == len(s):
              return len(s)
          for i in range(len(s)):
              stack = [s[i]]
              leng = 1
              for j in range(i + 1, len(s)):
                  if s[j] not in stack:
                      stack.append(s[j])
                      leng += 1
                  else:
                      break
              max_len = max(len(stack), max_len)
              max_len = max(leng, max_len)
          return max_len

  파이썬을 파이썬답게 쓰고 싶어서 머리를 굴리는데.. 알고리즘은 결국 파이썬 답게보다 알고리즘 답게 쓰는게 좋은거같다.