[leetcode 2024/02/07] 3.Longest Substring Without Repeating Characters

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

LeetCode - The World's Leading Online Programming Learning Platform

 

1. 접근 방법

이번 문제는 겹치지 않는 문자열에 대해서 최대 길이를 출력하는 것이다.

 

Input: s= "abcabcbb" 가 들어왔을 때, "abc" 를 한 예로 들 수 있으며 길이가 3 이므로 3을 출력해주어야 한다.

처음에 문제 이해를 잘 못해서, 겹치는 문자열 -> 연속되게 겹치는 문자열에 해당한다고 생각했다.

 

따라서, abcc에서 c가 나왔을 때, 문자열 세는 과정을 멈추고 현재까지의 문자열을 저장한 후 다시 문자열을 세기 시작했었다. 

하지만, abcad 와 같은 경우 아래의 코드 (처음에 실패한 코드) 를 이용하게 되면,

abc, ad 로 나뉘게 된다. 긴 문자열을 bcad 임에도 불구하고 말이다.

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        result = []
        dict_length = defaultdict(int)
        for i in s:
            if i in dict_length:
                result.append(len(dict_length))
                dict_length.clear()
                dict_length[i] = 1
            else:
                dict_length[i] = 1
        result.append(len(dict_length))

        return max(result)

이 코드는, abcad 와 같은 문자열을 포함하지 못한다.

 

이에 고민을 하다가, for 문으로 문자열을 하나씩 읽기로 했다.

abcabcbb 이면,

a를 받아들이고, a 부터 시작해서 겹치는 문자들이 나올 때까지 읽기를 진행 -> 겹친다면 문자열 길이 저장 후 break

다시.. 다음 for 문의 값인 b 부터

b를 받아들이고, b 부터 시작해서 겹치는 문자들이 나올 때까지 읽기를 진행 -> 겹친다면 문자열 길이 저장 후 break

... 이를 반복한다.

 

코드 진행 과정을 간략히 적어보면,

[a]: index 0

abc -> 다음이 a 가 출력 되므로 멈춤 -> 길이 3 저장

 

[b]: index 1

bca -> 다음이 b가 출력 되므로 멈춤 -> 길이 3 저장

 

[c]: index 2

cab -> 다음이 c가 출력되므로 멈춤 -> 길이 3 저장

...

이를 반복한다.

 

이후 길이가 저장된 list에서 max 값을 출력해주었다.

 

예외 처리:

input으로 s = "" 이 들어오면 for 문을 돌지 않고 max(result)를 return 하게 된다.

따라서, for 문 밖에 

result.append(len(dict_length))

을 해주어, 비어있는 dict_length 의 길이를 result에 저장해서 0 이 출력되도록 하였다.

 

이번 코드는 뭔가 for 문을 2개 써서 O(n^2) 에 복잡도를 가진 것이 마음에 들지 않는다.

 

다시 한번 코드를 보고 공부할 것이다.

 

2. 코드

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        result = []
        dict_length = defaultdict(int)
        for k in range (0, len(s), 1):
            dict_length.clear()
            for i in s[k:]:
                if i in dict_length:
                    result.append(len(dict_length))
                    dict_length.clear()
                    dict_length[i] = 1
                    break
                else:
                    dict_length[i] = 1
            result.append(len(dict_length))
        result.append(len(dict_length))
        return max(result)