[LeetCode] 3. Longest Substring Without Repeating Characters (Python)

LeetCode 3. Longest Substring Without Repeating Characters
String

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

Longest Substring Without Repeating Characters - LeetCode

1. 문제 설명

Longest Substring Without Repeating Characters은 이름 그대로 가장 긴 문자열을 의미한다.

이때, 같은 문자를 중복해서 사용하면 안된다.

 

LCS처럼 dp를 이용하여 풀 수도 있겠지만 (사실 고민해보지 않았다. 아마 가능하지 않을까..)

2차원 배열을 쓰지 않고, 그냥 문자열을 처음부터 끝까지 한 번만 돌면서 문자열이 중복되는지만 확인해주면 된다.

 

아래와 같은 문자열이 주어진다고 가정하자.

s = "abcabcbb"

이때 연속되는 문자열은 abc, bca, cab 등 최장 길이는 3이다.

따라서 3을 리턴해주면 된다.

---

2. 문제 접근

Naive approach

이 문제는 사실 Dynamic Programming, Greedy 등 여러 기법보다는 그냥 Naive하게 루프 한 번에 끝냈다.

중복된 문자가 나온다면 최장 문자열의 길이를 업데이트 하고, 새로운 substring을 만들면 된다.

 

다만, 이 루프를 돌면서 새로운 문자열을 제대로 만들어 주어야 한다.

예제처럼 string이 "abcabcbb"으로 주어졌다면 substring을 공백으로 초기화해도 큰 상관이 없을 것이다.

 

그러나 공백으로 초기화하면 반례가 존재한다.

예를 들어 아래와 같은 문자열이 주어진다고 가정하자.

s = "dvdf"

'dvdf'같은 문자열의 경우 세 번째 인덱스인 'd'가 들어와서 공백으로 초기화하면 substring을 'd'로 잡을 것이다.

하지만, 'd' 앞에 있는 'v'도 함께 포함하는 것이 제일 긴 substring이다.

따라서 substring에서 해당 문자의 다음 인덱스부터 마지막 문자열 + 중복되는 문자로 구성된 새로운 substring을 만들어 주어야 한다.

---

3. 참고 사항

① 리턴 값에 최대값이 정해진 경우는 루프의 탈출 조건을 걸어두는 것이 좋다.

해당 문제에서 문자열의 최장 길이는 5 * 10⁴이므로 상당히 길다.

따라서 중간에 문자열의 길이가 알파벳의 최대 개수(= 26)인 경우 즉시 리턴하는 것이다.

 

② 루프가 끝나는 시점에도 최대값을 업데이트 해야 한다.

중복된 문자가 들어오는 경우만 최대값을 업데이트하면 루프 종료시점의 substring의 길이를 반영할 수 없다.

따라서 리턴하는 시점에 마지막으로 최대값을 업데이트 해야 한다. 

 

 

---

4. 구현 코드

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        string = []
        res = 0
        for i in s:
            if i not in string:
                string.append(i)
            else:
                res = max(res, len(string))
                idx = string.index(i)
                string = string[idx + 1:]  # 중복되는 문자열의 다음 인덱스부터 잡는다!
                string.append(i)

            if res == 26:  # 알파벳 최대 개수인 경우 즉시 리턴
                break

        return max(res, len(string))

 

제출 결과 상위 8.27%의 런타임으로 코드가 통과했음을 알 수 있다.

리스트에 in을 사용하는 것이 O(n)이라 런타임이 조금 걱정되긴 했으나, 만족스러운 결과를 받았다.