3. Longest Substring Without Repeating Characters

Problem

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

A substring is a contiguous non-empty sequence of characters within a string.

https://leetcode.com/problems/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.

Constraints:

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

Test Cases

1 2	class Solution: def lengthOfLongestSubstring(self, s: str) -> int:

solution_test.py

import pytest

from solution import Solution
from solution2 import Solution as Solution2


@pytest.mark.parametrize('s, expected', [
    ('abcabcbb', 3),
    ('bbbbb', 1),
    ('pwwkew', 3),
])
class Test:
    def test_solution(self, s, expected):
        sol = Solution()
        assert sol.lengthOfLongestSubstring(s) == expected

    def test_solution2(self, s, expected):
        sol = Solution2()
        assert sol.lengthOfLongestSubstring(s) == expected

Thoughts

从第一个字符开始，这时候 substring 长度为 1。

设当前的 substring 范围是 [i, j]。把范围向右扩大到 [i, j+1]，要检查是否包含 repeating chars 并做出调整。

从 i 到 j 逐个与 j+1 位置的字符比较，假设 s[k] == s[j+1]，则把范围缩小为 [k+1, j+1]。

用一个变量记录见到过的最长的 substring 长度。

假设所求的 longest substring 长度为 m，时间复杂度为 O(m*n)，空间复杂度 O(1)。

Code

solution.py

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        n = len(s)
        if n <= 1:
           return n

        i, j = 0, 1
        max_len = j - i
        while j < n:
            # Current substring is s[i:j].
            # Try extend it to s[i:j+1].
            # Check if there is a `k`, i <= k < j, s[k] == s[j].
            for k in range(i, j):
                if s[k] == s[j]:
                    i = k + 1
                    break

            j += 1
            max_len = max(max_len, j - i)

        return max_len

快一些

如果用哈希表动态地记录当前 substring 中的字符（key 是字符，value 是位置下标），则时间复杂度为 O(n)（基本上每个字符都会入栈一次，出栈一次），空间复杂度为 O(m)。

solution2.py

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        n = len(s)
        if n <= 1:
           return n

        i, j = 0, 1
        max_len = j - i
        chars = {s[i]: i}
        while j < n:
            # Current substring is s[i:j].
            # Try extend it to s[i:j+1].
            # Check if there is a `k`, i <= k < j, s[k] == s[j].
            # Also update chars, remove s[i:k+1], add s[j].
            k = chars.get(s[j], -1)
            while i <= k:
                chars.pop(s[i])
                i += 1

            chars[s[j]] = j

            j += 1
            max_len = max(max_len, j - i)

        return max_len

本文除了题目描述（Problem）部分之外，其他内容由 Calf 原创，采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。