🤔 문제 : Longest Substring Without Repeating Characters | LeetCode 779
문제: https://leetcode.com/explore/interview/card/top-interview-questions-medium/103/array-and-strings/779/
어떤 문자열이 주어졋을 때
- 그 문자열의 substring중에서
- substring내에 중복된 character가 없고
- 길이가 가장 긴 substring
위 조건에 맞는 substring의 길이를 반환하는 문제입니다.
💡 풀이
1. 중복 character의 index를 기록하여 substring길이 계산
1. 주어진 문자열을 순회하며, 이전에 나온 character와 중복된 character가 있는지 확인
2. 중복된 character가 나타나면, 이전에 나왔던 character위치부터 substring을 다시 만들어나감
위의 로직으로 아래와 같은 코드를 작성하였습니다.
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
st_index = -1
max_length = 0
curr_length = 0
char_set = {}
for idx, c in enumerate(s):
if c in char_set and char_set[c] >= st_index:#[4]
st_index = char_set[c] # [2]
char_set[c] = idx # [1]
curr_length = idx - st_index # [3]
max_length = max(curr_length, max_length)
# print(c, char_set, curr_length, max_length)
return max_length[1] c가 가장 마지막으로 나온 index를 char_set dictionary에 기록해둡니다.
[2] c가 중복문자인 경우, 가장 최근에 나왔던 지점이 이 substring의 시작점이 됩니다.
예를들어, abcab라는 문자열이 있다면 앞에서부터 읽어나가며 아래와 같이 substring을 구성합니다.
| a ab abc |
[3] 현재 substring의 길이를 계산합니다.
[4] c가 중복문자인지 확인하는 부분입니다. 시작점 이후에 해당 문자열이 나온적이 있는지를 확인합니다.
Time Complexity
문자열의 모든 문자에 대해(N) charset을 탐색(logN)하며 중복여부를 확인하므로
O(NlogN)
Space Complexity
별도 공간을 만들지 않음
2. String Split 활용
더 깔끔한 코드가 있나 찾아봤는데, input이 String임을 활용하여 Split을 활용한 깔끔한 코드가 있어 정리해둡니다.
def lengthOfLongestSubstring(self, s: str) -> int:
max_length = 0
substr = ""
for c in s:
if c in substr: substr = substr.split(c)[1] + c
else:
substr += i
max_length = max(max_length, len(substr))
return max_length
로직은 1번풀이와 거의 유사한데 Runtime이 더 빠르네요.
1번의 경우 이미 지나간 char에 대한 set도 포함하고 있어 불필요한 비교연산을 수행하는 부분에서 비효율성이 발생한 것 같습니다.
Wrong Answers,,
사실 이 문제에서 급하게 문제를 먼저 풀다가 여러번 WA를 받았습니다.
고려하지 않았던 테스트케이스들은 아래와 같습니다.
"", " "
- 문자열이 아예 들어오지 않거나, 1글자 짜리가 들어오는 케이스..
- input에 공백이 들어올 수도 있음
"dvdf"
- 처음에는 연속된 문자가 있는 경우에만 substring을 끊는걸로 생각함
"abba"
- 업데이트된 start index이전에 나온 중복 문자를 고려하지 않음
