Python Algorithm Q30

January 28, 2022

Q30 Longest Substring Without Repeating Characters

Q

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

Sample Input

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.

Constraints

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

1. My Own Solution

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        def expand(left: int, right : int) -> str:
            temp = set() #to check whether already appeared or not
            
            while left>=0 and right<len(s) and (s[left] not in temp) and (s[right] not in temp):
                if (right != left) and (s[right] == s[left]):
                    break
                temp.add(s[left])
                temp.add(s[right])
                left -= 1
                right +=1  
            return s[left + 1:right]

        result = ''
        for i in range(len(s)):
            result = max(result, expand(i, i+1), expand(i, i), key=len)

        return len(result)

이전에 풀었던 문제(Q6 가장 긴 팰린드롬 부분 문자열)에서 등장했던 풀이가 문득 떠올라서 응용해본 것이다. 이 풀이에서는 슬라이딩 윈도우를 이용해서 풀었다. String을 따라가면서 모든 문자마다 확장을 시도하고, max로 비교하는 방식이다. 구현 자체는 그리 어렵지 않았다. 간단히 설명하겠다.

palindrome에서는 새로 추가되는 좌우가 같은지 아닌지만 판단하면 됐지만, 여기선 기존에 등장했는지 아닌지를 계속 체크해야 한다. 따라서 set을 이용해서 확인했다.

while left>=0 and right<len(s) and \
(s[left] not in temp) and (s[right] not in temp):
    if (right != left) and (s[right] == s[left]):
            break

매 loop마다 다음과 같은 사항들을 확인한다.

좌우 edge에 닿지 않았는가
s[left] 원소가 set에 담겨있지 않은가
s[right] 원소가 set에 담겨있지 않은가

추가적으로 break를 위해 right와 left가 같지 않은데 그 원소들 s[left], s[right]가 같은 경우에 거를 수 있도록 if-break를 넣었다. 나머지 원리들은 동일하다.

이렇게 풀면 자력으로 풀리기는 풀리는데 런타임이 진짜 미쳤다… 너무 오래 걸린다. 슬라이딩 윈도우로 일일히 쓸고 지나가는 만큼 시간복잡도가 올라가는 것 같다. 그리고 이 챕터의 해시 테이블을 제대로 이용하지 못하는 것 같아서 여러모로 좀 아쉬운 풀이이다.

2. Given Solution #1

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        used = {}
        max_len = start = 0
        for index, char in enumerate(s):
            if char in used and start <= used[char]:
                start = used[char] + 1 #char = key, index = value
            else:
                max_len = max(max_len, index - start + 1)

            used[char] = index
    
    return max_len

책에서 주어진 풀이는 index를 초점으로 전개해나가는 풀이이다. enumerate를 이용해서 given string을 각각의 char로 분해한다. 매번 index와 char을 이용해 for loop를 돌린다.

1) char이 이미 used dic에 들어가 있을 경우에 start 포인트를 새로 갱신한다. 이때 새로운 시작점은 used dic에 저장되어있는 중복된 문자의 다음 위치이다. 뭔소린지 잘 이해가 안갈 수 있다. 예를들어, “a, b, c, a, b, c, b, b” 라는 test case가 있으면 네번째 a:3이 for loop에 들어가면 start는 index = 3 + 1이 아니라, 첫번째로 a가 나타난 0 + 1로 시작한다는 것이다. 그래야지만 누락되는 case 없이 다 검토할 수 있다.

*start를 갱신할 때 현재 슬라이딩 윈도우의 바깥에 있는 문자는 예전에 등장한 적이 있더라도 무시해야하기 때문에 start <= used[char]를 if문에 추가해 준다. 새로운 loop때 기존 dictionary를 따로 비우지 않기 때문이다.

2) char이 used dic에 들어있지 않은 새로운 문자인 경우에는 max_len을 갱신한다(max 함수를 이용해 기존 max와 비교). 이때 length는 지금 test한 문자의 index에서 (위에 언급된 방식으로 갱신되는)시작점인 start을 빼고 1을 더해서 구한다. “0, 1, 2” 까지면 사이즈가 3(=2 - 0 + 1)으로 계산되기 때문. 이후 dictionary에 현재 char을 key로, index를 value로써 used dic에 추가해준다.

3. Given Solution #2

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        charSet = set()
        left = 0
        result = 0
        for right in range(len(s)):
            while s[right] in charSet:
                charSet.remove(s[left])
                left += 1
            charSet.add(s[right])
            result = max(result, right-left+1)
        return result

leetcode에서 긁어온 풀이. left는 #2 풀이에서의 start와 비슷한 맥락이다. while문이 실행되는지 아닌지에 따라 나누어 살펴보자.

charSet에 s[right]가 들어있지 않은 경우
charSet에 s[right]을 집어넣고 현재 index(=right)에서 시작점(=left)를 빼고 1을 더해서 그 길이를 이전 최대길이와 비교한다.
charSet에 s[right]가 들어있는 경우
왜 갑자기 s[left]를 set에서 제거하는지 의문이 든다면 예시를 통해 확인해보자. “abc/bca/bb”라는 코드가 있다고 하자(/는 무시하자). 처음에 abc는 중복되지 않게 1번 방식으로 3번 진행되고 set은 [a, b, c]와 같다. 이제 중복되는 b가 입력되는 순간, 먼저 입력되어 set에 들어간 b 앞에 얼마나 많은 알파벳이 있었는지는 무의미하게 싹다 초기화 시켜야한다. 즉 “xyzasdfghb/cvty/b”라는 식이면 앞에 “xyzasdfgh”를 while문에서 차례차례 날리고(by left += 1) 마지막에 먼저 있던 b까지 날리면 이제 while loop에서 나간다.

#2번 풀이와 상당히 유사한 점이 많다. #2번 풀이는 dic은 유지시켜 놓고 start point만을 바꾸어 진행했다면, 이 풀이는 set을 만들고 주기적으로 insertion과 deletion을 반복해서 진행했다.

Overall Review

왜 맨날 내 풀이는 메모리는 덜 쳐먹는데 런타임은 더럽게 긴지 모르겠다… 나름 직관적이게 푼 것 같은데 런타임이 저리 오래 걸려서야 문제가 이래저래 많은 것 같다. 책에서 주어진 풀이나 다른 사람들의 코드를 보면 되게 깔끔하게 풀었던데 조금 고민해서 이런 풀이를 뽑아낼 수 있는 실력을 쌓으려면 얼마나 공부를 더 해야할지 너무 막연하게 느껴지는 것 같다.

Hyuntae H