[LeetCode 리트코드] Longest Substring Without Repeating Characters , python3

문제

문자열 s가 주어진다. s의 substring중에서 중복된 문자가 없는 substring의 최대 길이를 리턴하라.

예

input : s = "abcabcbb"

output : 3 

추가사항

 

• 0 <= s.length <= 5 * 10^4
• s 에는 영어, 공백, 숫자, 특수문자 가 올 수 있음

 

 

나의 솔루션_1 (정말 느려 터짐)

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        
        if len(s) == 1:
            return 1
        
        result = 0
        for idx, _ in enumerate(s):
            for i, sub in enumerate(s[idx:]):
                tmp = s[idx:idx+i+1]
                #set으로 만들어서 본래 문자의 길이가 같으면 중복이 없는 것으로 간주
                if len(tmp) ==  len(set(tmp)):
                    result = max(result, len(tmp))
                else:
                    break
        return result

정말 느리다 ㅋㅋㅋ 로직은 Brute Force와 비슷한데 tmp를 만들고, 비교하는 부분이 상당히 부하가 많이 걸리나보다.

결과가 자그마치 4528 ms 가 나왔다. 대부분의 결과들이 100ms 이하인데, 나의 결과가 4천대라니 ㅋㅋㅋㅋ

 결과

 

솔루션_2 Sliding Window

리트코드의 최 장점은 솔루션을 보면서 공부할 수 있다는 점이다. 이번 문제는 심지어 동영상 강의까지 있다. 

Algorithm 설명 (-> 한국어 번역)

The naive approach is very straightforward. But it is too slow. So how can we optimize it?
-> 단순한 접근은 상당히 직관적이지만 매우 느리다. 어떻게 최적화할 수 있는가?

In the naive approaches, we repeatedly check a substring to see if it has duplicate character. But it is unnecessary. If a substring s[i:j]​ from index i to j - 1 is already checked to have no duplicate characters. We only need to check if s[j] is already in the substring s[i:j].​
-> 단순한 접근에서 우리는 반복적으로 substring에 중복된 문자가 있는지 체크한다. 하지만 이는 불필요하다. 만약 s[i:j)까지 이미 중복된 문자가 없다고 체크를 했다면, 우리는 s[j]가 s[i:j]에 있는지 없는지만 체크하면 되기 때문이다.

To check if a character is already in the substring, we can scan the substring, which leads to an O(n^2) algorithm. But we can do better.
-> 한 문자가 substring에 있는지 체크하기 위해서 우리는 substring을 스캔할 수 있다. 이는 O(n^2)인데 더 좋은 방법이 있다.

By using HashSet as a sliding window, checking if a character in the current can be done in O(1).
-> HashSet을 슬라이딩 윈도우로 사용하여, 현재 가리키고 있는 문자가 중복인지 O(1)로 체크할 수 있다.

A sliding window is an abstract concept commonly used in array/string problems. A window is a range of elements in the array/string which usually defined by the start and end indices, i.e. [i, j) (left-closed, right-open). A sliding window is a window "slides" its two boundaries to the certain direction. For example, if we slide [i, j) to the right by 1 element, then it becomes [i+1, j+1)(left-closed, right-open).
-> 슬라이딩 윈도우는 array혹은  string 문제들에서 흔히 쓰이는 추상적인 개념이다. 윈도우는 array혹은 string의 i번째~j-1번째로 이루어진 범위를 말한다. 슬라이딩 윈도우는 양 쪽 경계를 한쪽 방향으로 슬라이드 하는 윈도우를 말한다. 예를 들어, [i, j)를 1만큼 슬라이드 하는 것은 [i+1, j+1) 가 된다.

Back to our problem. We use HashSet to store the characters in current window [i, j)(j = i initially). Then we slide the index j to the right. If it is not in the HashSet, we slide j further. Doing so until s[j] is already in the HashSet. At this point, we found the maximum size of substrings without duplicate characters start with index i. If we do this for all i, we get our answer.

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

Longest Substring Without Repeating Characters - LeetCode

위 방법을 적용한 코드

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        result = 0
        i = j = 0
        length = len(s)
        charSet = set()
        while i < length and j < length:
            if s[j] not in charSet:
                charSet.add(s[j])
                result = max(result, j-i+1)
                j += 1
            else:
                charSet.remove(s[i])
                i += 1
        return result
            

결과가 놀랍게도 엄청나게 빨라졌다. WOW..... 역시 O(n^3) 과 O(n)의 차이는 어마어마하다.

 결과

 

솔루션_3 Sliding Window Optimized

조금 더 최적화 된 해답이다. 위의 슬라이딩 윈도우는 O(2n)인데, 이 방법은 O(n)이다.

The above solution requires at most 2n steps. In fact, it could be optimized to require only n steps. Instead of using a set to tell if a character exists or not, we could define a mapping of the characters to its index. Then we can skip the characters immediately when we found a repeated character.
-> 위의 해답은 2n만큼 걸린다. 하지만 n만 걸리는 더 최적화된 해답이 있다. set을 사용하여 문자가 있는지 확인하는 대신, 문자의 index를 매핑하여 정의하는 방법이 있다. 중복된 문자를 찾게되면 그 문자를 바로 건너뛸 수 있다.

The reason is that if s[j] have a duplicate in the range [i, j) with index j', we don't need to increase i little by little. We can skip all the elements in the range [i, j'] and let i to be j' + 1directly.

위 방법을 적용한 코드

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        result = 0
        i = 0
        length = len(s)
        charMap = {}
        for j in range(length):
            if s[j] in charMap:
                i = max(charMap[s[j]], i)
                
            result = max(result, j - i + 1)
            charMap[s[j]] = j+1
            
        return result
            

근데 이상한 것이 두 번째 방법보다 최적화 된건데 더 느리다는 점.... 왜일까?

 결과

깨달은 점

이런 substring 문제는 늘 자주 출제되는데 막무가내로 풀 때가 많았다. 이제 슬라이딩 윈도우를 공부했으니 이제부터는 이를 활용해서 문제를 풀어야겠다.