LeetCode - 3. Longest Substring Without Repeating Characters

[LeetCode] 3. Longest Substring Without Repeating Characters

LeetCode 3번 문제를 풀어보았다.. Link

Problem

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

Intuition

Substring이 시작하는 곳을 start, 끝나는 곳을 end라고 할 때, start와 end 를 움직여가며 조건(without repeating characters)에 충족하는 모든 Substring의 길이를 비교하여 그 중 가장 긴 길이를 출력하면 될거라고 생각했다.

놀랍게도 처음에 풀 때는 그냥 수월하게 풀었는데 다시 풀 때 더 시간이 오래 걸렸다. 체계적인 복습이 중요하다..

Approach

모든 케이스를 전부 비교하는 Brute Force 알고리즘으로 풀었다.

1. s[start:end] 안에 s[end]가 있는지 확인한다.
   1. 없으면 그때의 s[start:end]의 길이를 측정하고, max_length와 비교한다.
      1. max_length보다 작으면 end point를 한칸 옮긴다.
      2. max_length보다 크면 max_length를 end - start + 1로 update한다.
   2. 있으면 max_length를 비교한다.
      1. max_length보다 크면 max_length를 end - start로 update한다.
      2. start point를 한칸 옮긴다.
2. start point가 len(s)-1에 도달할 때 까지 반복한다.

Complexity

• Time complexity:

  이중 for loop로, \(O(n^2)\)라고 착각할 수 있지만, 문자열 Slice와의 비교가 있기 때문에 \(O(n^3)\)이다.

  (이건 정확하지 않음..)

• Space complexity: 문자열에 중복 문자가 없는지 확인하는데는 \(O(n)\)이 필요하다.

My Code

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        """
        Input: A string "s"
        Output: The length or the longest substring without repeating characters.
        """
        max_length = 1
        if not s:
            return 0

        found = False
        for i in range(len(s)-1):
            for j in range(i+1, len(s)):
                if s[j] not in s[i:j]:
                    if max_length < j-i+1:
                        max_length = j-i+1
                else:
                    if max_length < j-i:
                        max_length = j-i
                    break

        return max_length

Others

Brute force을 사용한 내 풀이보다 더 효율적인 방법으로 최적화한 코드이다.

아이디어는 다음과 같다.

• 예를들어 “abcade”가 있다고 했을 때, 기존의 Brute force 알고리즘으로 처리한다면 “abc”, “a”에서 멈추게 된다.
• 이때 굳이 나머지 “de”를 다 본 다음 새로운 start와 end point를 “b”, “c”로 옮기는 것이 아니라 중복이 없는 선까지 start point만 옮기는 방법을 사용한다. (코드와 함께보면 이해할 수 있을까?)
• 또한 여기서 필요없는 search algorithm을 피하기 위해 Hash map (python에서는 Dictionary)를 활용한다.

class Solution:
    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        len_s = len(s)
        Mlength = 0
        dict = {}
        start = 0
        for end in range(len_s):
            if s[end] in dict:
                start = max(dict[end], start)
            Mlength = max(Mlength, end - start + 1)
            dict[s[end]] = j + 1
        return Mlength

• 이 Approach의 Time complexity는 한 반복(end) 안에 끝나기 때문에 \(O(n)\)이다.
• Space complexity도 Dictionary에 저장하는 공간을 생각하면 \(O(max(n, m))\)이다.