리트코드 - longest substring without repeating characters.

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

Longest Substring Without Repeating Characters - LeetCode

문자열 s가 주어지면, 반복되는 문자 없기 가장 긴 하위 문자열을 구하는 것이다. - 하위 문자열이란 문자열 내에서 연속적인 시퀀스이다.

 

해당 문제는 예전에 비슷한 문제를 풀어봤던 기억이 있어서 풀이를 쉽게 생각할 수 있었다.

연속적인 시퀀스인 점 + 반복되는 문자가 없다는 특징을 주목한다.

 

이를 위해서 문자열을 순회하면서 각 루프마다 가장 긴 하위 문자열을 저장하는 리스트를 하나 생성했다.

그리고 매 루프마다 리스트에 해당 문자열이 있는지 확인하고, 해당 문자열이 존재하지 않는다면 리스트에 해당 문자열을 추가했다.

해당 문자열이 존재한다면, 해당 문자열이 존재하지 않을 때까지 리스트의 0번째 인덱스를 제거했다. (하위 문자열의 조건인 연속성을 유지하기 위함) 그리고 해당 문자열을 추가했다.

 

그리고 각 루프마다 하위 문자열의 최대 길이를 갱신해주면, 모든 루프가 종료된 이후 최대 길이를 반환하도록 구현하였다.

문제가 있다면.. 만약 하위 문자열이 주어진 문자열과 같을 경우 최대 시간 복잡도가 O(n^2)라고 생각한다.

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        max_length = 0
        curr_word = []
        for string in s:
            if string not in curr_word:
                curr_word.append(string)
            else:
                while string in curr_word:
                    del curr_word[0]
                curr_word.append(string)
            max_length = max(max_length, len(curr_word))
        return max_length

주말에 해당 문제에 대한 더 좋은 풀이를 고민 혹은 찾아봐야겠다.