[LeetCode]Longest Substring Without Repeating Characters

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

Longest Substring Without Repeating Characters - LeetCode

 

문제 분석

반복되는 문자 없이 가장 긴 부분 문자열을 구하는 문제입니다.

(Substring : 연속된 부분 문자열, Subsequence : 연속은 상관 없이 순서만 맞아도 되는 부분 문자열)

 

첫번째 답안

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        # 문자열이 고유한 단어들로만 이루어진 경우, 문자열의 길이 자체가 정답입니다.
        if len(set(s)) == len(s):
            return len(s)
        substring = ''
        max_len = 1
        
        for i in s:
            # substring에 들어있지 않은 문자인 경우에만 substring을 추가하고, max_len 값을 업데이트 합니다.
            if i not in substring: 
                substring = substring + i
                max_len = max(max_len, len(substring))       
            # 이미 substring에 있는 문자가 다시 등장한다면
            # 이전에 등장한 문자 앞부분을 버리고 새롭게 substring을 시작합니다.
            else:
                substring = substring.split(i)[1] + i         
        return max_len

접근 방법

1. 문자열이 고유한 단어들로만 이루어진 경우는 그 길이 자체로 정답입니다.
2. 문자열을 순회하면서 고유한 단어들로만 이루어질때 substring에 이어 붙입니다.
3. 이어 붙일 때 새로운 substring의 길이와, 현재의 max_len 중 큰 값으로 max_len을 갱신합니다.
4. 이미 substring에 들어있는 문자가 다시 등장한다면 중복으로 등장한 문자부터 앞부분을 버리고 substring을 새롭게 할당하여 시작합니다.
5. 순회를 완료하면 반복없는 가장 긴 문자열의 길이를 구할 수 있습니다.

단 1번의 순회만으로도 문제를 풀이할 수 있어서 신기했습니다. 이미 substring에 문자가 들어있는 것이 등장한다면 substring을 새롭게 초기화 하는 것이 인상깊었습니다.

 

이 문제의 경우 풀이를 하지 못해서 다른 사람들의 답안을 여러개 찾아보았습니다. 해당 답안은 아래 링크를 참고했습니다.

https://medium.com/the-research-nest/finding-the-longest-substring-without-repeating-characters-a-super-simplified-explanation-2f254a7ab11

Finding the longest substring without repeating characters: A super-simplified explanation

 

두번째 답안

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

접근 방법

1. 반복문을 순회하면서 커서와 인덱스 값을 활용합니다. 여기서 커서는 substring을 시작하는 위치를 나타냅니다.
2. 이미 substring에 들어있는 문자이고(사용한 문자), 커서의 위치가 사용한 문자의 위치보다 작거나 같다면 중복으로 등장한 문자입니다. 따라서, 커서의 위치를 사용한 문자 다음으로 옮겨줍니다.
3. 그렇지 않다면 새로운 문자이므로 해당 시점에서의 substring의 최대 길이를 갱신합니다.
4. 등장한 문자를 key로하고 위치(idx)를 value로 하여 해당 문자가 등장한 마지막 위치를 기록합니다.

이 알고리즘의 경우 일반적으로 sliding window 라고 불립니다. 사실 저는 첫번째 답안에 비해 이해하기에 힘들었는데 이런 방법으로도 풀이할 수 있다는 것을 알고가면 좋을 것 같습니다.