[코딩 테스트] 리트코드 3 - Longest Substring without Repeating Characters (Medium) in Python

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

문자열 s가 주어졌을 때, 반복되지 않는 문자로 이뤄진 가장 긴 부분문자열의 길이를 리턴하세요!

 

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

 

• 0 <= s.length <= 5 * 104
• s consists of English letters, digits, symbols and spaces.

 

풀이

입력으로 넣어진 문자열 s를 한 글자 한 글자 탐색하면서,

각 글자가 이미 탐색되었으면 부분 문자열의 시작점을 갱신해주는 코드를 짠다.

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        dic, start, answer = {}, 0, 0 # dic은 각 문자가 나타난 index를 저장해준다.
        n = len(s)
        for i in range(n): # 문자열 s를 처음부터 끝까지 탐색함
            if s[i] in dic: # 지금 살펴보고 있는 문자 s[i]가 이미 나타났던 문자라면
                start = max(start, dic[s[i]] + 1) # 부분 문자열의 시작점을 갱신해준다.
            dic[s[i]] = i # dic에 s[i]가 나타나는 index를 갱신
            answer = max(answer, i - start + 1) # 현재 answer에 저장된 값과, 현재 부분 문자열의 길이 중 더 큰 값을 저장
        return answer

문자열을 쭉 한 번 탐색하고, dic에 있는 원소에 접근하는 것은 상수 시간을 요하므로 전체 시간 복잡도는 O(n) * O(1) = O(n)이 되겠다.

공간 복잡도는 dic (hash table)이 따로 필요하니 O(n).