[python] LeetCode 3번: Longest Substring Without Repeating Characters(medium)

in Algorithm on LeetCode
[python] LeetCode 3번: Longest Substring Without Repeating Characters(medium)

Problem

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

0 <= s.length <= 5 * 104
s consists of English letters, digits, symbols and spaces.

문자열 s가 주어졌을 때, 중복되는 문자가 없는 가장 긴 부분문자열의 길이를 찾아라.

문제 링크 : 리트코드 3번

<Try>

이 문제를 비롯하여 문자열 중 어떠한 특징을 지닌 부분문자열의 최대 혹은 최소 길이를 반환하는 문제가 종종 나온다. 이러한 유형의 문제 대부분은 DP로 풀린다.

이 문제의 경우 DP 개념에 부분문자열의 시작과 끝을 정해주는 투 포인터를 적용하여 접근하였다.


<Solution>

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        start = 0   # 부분 문자열의 첫 문자의 index(초기값:0)
        dic = {}    # 문자들의 가장 마지막 위치의 인덱스를 담은 딕셔너리
        max_len = 0     # 나온 길이 중 최대 길이
        curr_len = 0    # 특정 문자 위치에서 가질 수 있는 최장 부분문자열의 길이
        for i, v in enumerate(s):
            if v not in dic:    # 처음 나오는 문자면 dic에 등록하고 현재 길이 1 증가
                dic[v] = i
                curr_len += 1
            else:   # 중복되는 문자가 나왔을 때
                if dic[v] >= start:     # 현재 부분문자열 내에 중복되는 문자가 포함
                    start = dic[v] + 1  # 시작 인덱스 변경
                    curr_len = i - dic[v]   # 변경된 현재 길이
                    dic[v] = i      # 중복된 문자의 마지막 위치 인덱스 갱신
                else:   # 현재 부분문자열 내에 포함되지 않아 영향이 없을 때
                    dic[v] = i
                    curr_len += 1
            
            if curr_len > max_len:
                max_len = curr_len
        
        return max_len

문자열을 순회하면서 마주칠 수 있는 case들을 나누어 접근하면 쉽게 생각할 수 있다.

  • 문자가 처음 나왔을 때: 딕셔너리에 새로운 문자 등록, curr_len +1
  • 중복되는 문자가 나오고 현재 부분문자열에 포함될 때: start 및 curr_len 변경
  • 중복되는 문자가 나오고 현재 부분문자열에 미포함일 때: 중복 문자 인덱스 수정 및 curr_len +1

전체 문자열 s를 1회 순회하므로 시간 복잡도는 O(n)이다.

© 2020. All rights reserved.