[Leetcode 아주 상세한 문제풀이] 3. Longest Substring Without Repeating Characters - 코드 line 별 설명

Leetcode 문제

이번에 풀어볼 문제는 리트코드 3번 문제 Longest Substring Without Repeating Characters 다.

우선 문제는 다음과 같다.

 

리트코드 3번 문제 Longest Substring Without Repeating Characters 링크

Longest Substring Without Repeating Characters - LeetCode

Longest Substring Without Repeating Characters - LeetCode

 

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

 

Example 1:
Input: s = "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.

Example 2:
Input: s = "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.

Example 3:
Input: s = "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3.
Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.

 

 

문제 설명

문제에 대해 간략히 설명하면 주어진 문자배열 s가 있을 때 문자가 반복되지 않는 가장 긴 substring의 길이를 찾아내는 문제다. 예를 들어 1번 예시의 경우 첫번째 인덱스부터 탐색하다보면 abc까지는 서로 겹치는 문자가 없지만 네번째 자리에서 a가 반복되기 때문에 가장 긴 substring의 개수는 3 (i.e., abc)이라고 할 수 있다. 여기서 주의할 점은 이 문제는 substring을 찾는 것이지 subsequence를 찾는것이 아니다 (3번 예시). 참고로 Substring은 연속된 문자배열이고, subsequence는 순서가 유지된 문자배열이되 그 사이에 있는 문자열을 삭제함으로써 얻어지는 문자배열이다.

 

 

문제 접근법

이제 문제를 풀어보자.

우선 이 문제에 대한 접근 방법 포인터 (start, end)와 dictionary를 이용하는 것인데,

포인터를 입력된 문자열 첫번째 인덱스부터 탐색하며

문자열이 dictionary에 들어있다면 start 포인터를 다음 인덱스로 하나 옮기고

문자열이 dictionary에 들어있지 않다면 그 문자열을 dictionary에 추가한다.

이때 반복되지 않는 문자열의 길이를 max_len로 카운트해줘야 하는데

max_len가 max (max_len, end-start+1)로 정의되는 이유는

입력된 문자열에 반복되지 않는 문자열이 여러개 존재할 수 있기 때문인데

예를 들어 abcbefgh 같은 문자열의 경우 반복되지 않는 문자열이 abc와 befgh 두개 존재하는데

이때 더 긴 문자열의 길이를 찾는 것이므로 기존에 가장 길었던 max_len (=3)과 마지막에 찾은 문자열의 길이 5 (befgh)를 비교해 더 긴 문자열을 출력해야 한다.

 

 

문제 풀이

우선 문자열을 받을 함수를 정의해 준다. (line 1)

그 후 dictionary와 max_len, start 포인터를 초기화해준다 (line 2-4)

그리고 문자열 길이만큼 첫번째 인덱스 부터 하나하나 문자열을 탐색한다 (line 6)

해당 인덱스의 문자열이 dictionary안에 존재한다면 그 지점 +1 부터 다시 검색을 시작한다 (line 10)

이 부분이 조금 헷갈릴수 있는데,

예를 들어 문자열이 'abcbd'로 주어진다면 end=3일 때 'b'가 겹치게 된다.

따라서 이 경우 b 다음부터 문자열을 다시 탐색해야 하기 때문에

'b'가 dictionary에서 차지하는 값 인덱스 값 1에 1을 더해 인덱스 값이 2인 ''c'부터 다시 탐색하면 된다.

문제풀이도 돌아와 만약 해당 인덱스 해당하는 문자열이 dictionary에 없다면

그 문자열을 dictionary에 추가하고 max_len를 업데이트 해준다.

 

 

문제 풀이 코드

def lengthOfLongestSubstring(s):
    char_dict = {}  # Dictionary to store the most recent occurrence of each character
    max_len = 0
    start = 0
 
    for end in range(len(s)):
        if s[end] in char_dict:
            # If the current character is already in the dictionary,
            # update the start pointer to the next index of the repeating character
            start = max(start, char_dict[s[end]] + 1)
 
        char_dict[s[end]] = end  # Update the most recent occurrence of the character
        max_len = max(max_len, end - start + 1)
 
    return max_len
 
s = 'abcbd'
print(lengthOfLongestSubstring(s))