LeetCode

Appearance

3. Longest Substring Without Repeating Characters ​

题目 ​

Given a string s, find the length of the longest substring without duplicate 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 * 104
  • s consists of English letters, digits, symbols and spaces.
Related Topics
  • 哈希表
  • 字符串
  • 滑动窗口

  • 👍 10825
  • 👎 0

    • 思路 ​

    解法 ​

    py
    # leetcode submit region begin(Prohibit modification and deletion)
class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        ans = 0
        start = 0
        hashMap = {}
        for i, char in enumerate(s):
            if char in hashMap:
                # start 为递增数列，该限制条件可约束 start 越界重置
                start = max(start, hashMap[char] + 1)
            hashMap[char] = i
            ans = max(ans, i - start + 1)

        return ans
# leetcode submit region end(Prohibit modification and deletion)

    复杂度分析 ​

    • 时间复杂度O(N)
      • N = len(s)
    • 空间复杂度O(1)
      • 字符的 ASCII 码范围为 0 ~ 127 ，哈希表 dic 最多使用 O(128)=O(1) 大小的额外空间