LeetCode 003 Longest Substring Without Repeating Characters

LeetCode 003 Longest Substring Without Repeating Characters

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

Example 1:

<pre>Input: s = "abcabcbb" Output: 3 Explanation: The answer is "abc", with the length of 3. </pre>

Example 2:

<pre>Input: s = "bbbbb" Output: 1 Explanation: The answer is "b", with the length of 1. </pre>

Example 3:

<pre>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. </pre>

Example 4:

<pre>Input: s = "" Output: 0 </pre>

Constraints:

• 0 <= s.length <= 5 * 10<sup>4</sup>
• s consists of English letters, digits, symbols and spaces.

题目大意：

求最长不重复子串。

解题思路：

HashMap和滑动窗口法，利用HashMap来记录这个窗口中所有字符的下标，该窗口中所有字符都不重复。
start_idx表示窗口的左界，而i是右界。左界=上次一次出现该字符的下标和目前左界的较大值，
因为Map中的某些字符可能已经不在窗口中，我没有把它从窗口中去掉，而是用start_idx来限制。

要计算长度就要先计算start_idx，步骤：

1. 计算start_idx
2. 计算长度

注意事项：

1. start_idx和前值比较，且只有当字符在map中才更新start_idx

Python代码：

def lengthOfLongestSubstring(self, s: str) -> int:
	start_idx, max_len = 0, 0
	char_map = {}
	for i in range(len(s)):
		if s[i] in char_map:
			start_idx = max(start_idx, char_map[s[i]] + 1)
		max_len = max(max_len, i - start_idx + 1)
		char_map[s[i]] = i
	return max_len

算法分析：

时间复杂度为O(n)，空间复杂度O(n)。