[LeetCode][Python] 3. Longest Substring Without Repeating Characters

- 문제 링크: https://leetcode.com/problems/longest-substring-without-repeating-characters/

 

문자열의 substring중에 문자열에 중복이 없는 것중 가장 긴 문자열의 길이를 구하는 문제입니다. 난이도는 medium 입니다.

일단 가장 먼저 생각해볼 수 있는건 브루트포스입니다. 모든 substring을 만들고 각 substring의 문자가 중복이 있는지 없는지 체크하는 O(n^3) 알고리즘이 있겠습니다. 당연히 TLE겠죠?

그래서 투포인터를 생각해볼 수 있겠는데요, 일단 문자열 하나를 만듭니다.

한글자씩 확인하면서 이미 앞에서 나온 문자면 해당 위치 앞까지 문자열에서 자르고, 그렇지 않으면 문자열 뒤에 append합니다. 매 단계마다 max_length를 저장해줍니다. 마지막으로 max_length를 반환하면 끝입니다.

def lengthOfLongestSubstring(self, s):
    str_list = []
    max_length = 0
    
    for x in s:
        if x in str_list:
            str_list = str_list[str_list.index(x)+1:]
            
        str_list.append(x)    
        max_length = max(max_length, len(str_list))
        
    return max_length

제 코드는 보기가 좀 그래서 wushi58 유저의 솔루션을 들고왔습니다.