Neunomizuの日記

俺だけが俺だけじゃない

# LeetCode Medium 3. Longest Substring Without Repeating Characters

tags: leetcode

問題

イデア

重複した文字を持たない最長の文字列の長さを返せという問題です.

今まで現れた文字列を保持するデータ構造を使えば良さそうです.

解法

  • 文字列のある部分を開始地点と終了地点までを見て,今までに現れた文字列があるかどうかで場合分けをします.
    • あれば,開始地点をずらします.
    • なければ,文字列の長さを更新します

計算量

文字列の長さを$N$とします.

  • 時間計算量
    • $O(N)$
  • 空間計算量
    • $O(N)$

Python

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        start = max_length = 0
        ans = 0
        used_char = {}
        for i in range(len(s)):
            if s[i] in used_char and start <= used_char[s[i]]:
                start = used_char[s[i]] + 1
            else:
                max_length = max(max_length, i - start + 1)
            used_char[s[i]] = i
        return max_length