Longest Substring Without Repeating Characters - leetcode(3)

Longest Substring Without Repeating Characters

요구사항

• Given a string s, find the length of the longest substring without repeating characters.
  => 문자열이 주어지면 같은 문자를 반복하지 않고 가장 길게 이어지는 문자열의 길이를 반환하세요.

Solution

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        # 같은 문자를 반복하지 않게, 이미 나온 문자라면 딕셔너리의 key에 문자를 value에 인덱스를 담는다.
        # 인덱스는 문자열 시작 위치를 파악하여 같은 문자가 나온다면 처음 나온 위치 +1로 시작 지점을 변경해줘야 한다.
        used = {}
        max_length = start = 0

        for index, char in enumerate(s):
            # if val in dict는 자주 사용되는 방법이다.
            # 일반적으로 이미 존재한다면 수를 늘려가는데, 여기서는 시작 지점을 늘려가는 것이다.
            if char in used and start <= used[char]:
                # 문자가 겹치면 안되기 때문에 이전의 위치 +1을하여야 현재 최대 길이를 구할 수 있는것이다.
                start = used[char] + 1
            else:
                # 기존의 최대 길이와 새로운 문자가 나왔을때 index - start + 1을 비교하여 더 높은게 제일 긴것이다.
                max_length = max(max_length, index - start + 1)
                
            # 반복문을 돌 때마다 문자의 위치를 최신화 시켜줘야 시작지점부터 끝나는곳 까지의 길이를 정확히 알 수 있다.
            used[char] = index

        return max_length

sol = Solution()

print(sol.lengthOfLongestSubstring("abcabcbb"))
# >>> 3

📌 코드 풀이

1. 반복문을 돌때 이미 존재하는 key를 담기 위해 dict()를 만들어 준다.
2. 시작 지점과, 최대 길이를 구해야되기 때문에 0을 할당하여 변수를 선언해둔다.
3. for반복문을 돌 때 enumerate에 문자열을 넣어서 인덱스와 값을 이용한다.
4. if 문자가 dict에 존재하고, dict에 있는 문자의 인덱스보다 현재 시작지점이 낮다면 시작 지점을 기존 문자가 존재하는 위치 +1로 해준다.
   => 이전에 나온 위치보다 +1을 하여야 중복되지 않은 문자열로 최대 길이를 구할 수 있다.
5. 문자가 dict에 존재하지 않는다면, max_len = max(max_len, index-start +1)로 최대 길이를 다시 구해준다.
   => 현재 포문을 도는 index - start(중복되는 문자가 없는 위치) + 1로 길이를 구할 수 있다.
6. 조건문이 끝났다면 used[char] = index로 가장 최근 나온 문자의 위치를 업데이트 해준다.
   => 같은 문자가 다시 나온다면 해당 위치이후 ~ 다시 나온 문자의 위치로 최대 길이를 구할 수 있는것이다.
7. 문제에서 요구한 max_length를 반환하면 끝이다.

leetcode

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