LeetCode Top Interview 150) Longest Substring Without Repeating Characters

Question

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

Constraints:

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

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:

---

---

영문자, 숫자 및 공백으로 이루어진 문자열 s가 주어집니다. 이 때 연속하는 하위 문자열 중 반복되는 문자를 가지지 않은 문자열의 최대 길이를 반환하는 문제입니다.

제가 생각한 코드는 다음과 같습니다.

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        subs = ''
        max_len = 0
        check_idx = 0

        for i,c in enumerate(s):
            check_idx = subs.find(c)

            if check_idx == -1:
                subs += c
            else:
                if len(subs) > max_len:
                    max_len = len(subs)
                subs = subs[check_idx+1:]+c

        return max(max_len,len(subs))

• subs : 하위 문자열을 저장하는 변수입니다.
• max_len : 최대 길이를 저장하는 변수입니다.
• check_idx : 반복되는 문자가 나왔을 때, 하위 문자열에서 해당 문자의 인덱스를 저장하는 변수입니다.
• 문자열을 돌면서 해당 문자가 하위 문자열 subs에 있는지 확인합니다.
  • find()함수는 찾고자 하는 문자가 없다면 -1을 반환합니다. 없다면 조건에 걸리지 않으므로 subs에 해당 문자를 추가합니다.
  • 문자가 subs에 있다면 우선 현재까지의 하위 문자열 길이와 max_len을 비교하여 큰 값을 저장합니다.
  • 그리고 하위 문자열은 이미 존재하는 문자의 인덱스인 check_idx보다 하나 큰 값부터 현재 문자까지로 저장합니다.
• 반복문이 끝나면 최대 길이와 len(subs)를 비교하여 큰 값을 반환합니다. 반복되는 문자가 없었을 때와 마지막 문자가 최대 길이에 포함되는 경우 max_len이 업데이트 되지 않는 경우가 있기 때문입니다.

---

생각보다 생각할 부분이 많았던 문제입니다.
우선 조건에서 알 수 있듯이 시간복잡도가 O(n^2)보다 작아야 한다는 것을 알 수 있습니다.

하지만 한 번의 반복문에서 해결하는건 아무리 생각해도 잘 안나오는듯해서 메모리를 좀 더 사용하는 방법을 생각했습니다.

집합을 사용해서 나오는 단어를 전부 저장하는 방식을 통해 반복을 하지않는 방법도 생각했지만 메모리를 너무 많이 사용하는 듯해서 위 방법으로 진행했습니다.

• 집합을 생각한 이유는 내부에 존재하는 원소를 가장 빨리 확인할 수 있는 자료구조이기 때문입니다. 순서를 지정할 수 없지만 그 외의 탐색에서 튜플이나 리스트에 비해 확실히 빠른 성능을 보입니다.

어쨌든 위 방법은 find()로 다소 반복이 있는 구조이지만 subs에서 인덱스를 확인하는 방법이고 최악이라도 O(n)에서 해결되는 방식입니다.

• 언뜻 find()를 반복해서 쓰기 때문에 O(n^2)으로 보일 수 있지만, 탐색하는 문자 전체를 보았을 때 겹치지 않게 탐색을 해나가므로 시간복잡도가 O(n)으로 마무리될 수 있습니다.

• 메모리는 0.1MB 차이로 백분율이 크게 움직이기 때문에 크게 신경쓰지 않아도 되었습니다.