HashTable经典题目详解
题目链接：
https://leetcode.cn/problems/longest-substring-without-repeating-characters/
Given a string s, find the length of the longest substring without repeating characters.
Example 1:

1
2
3
Input: s = "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.

Example 2:

1
2
3
Input: s = "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.

Example 3:

1
2
3
4
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.

解题思路：

定义一个哈希表 walkDict，用来记录每个字符最后一次出现的位置。
定义一个变量 begin，表示当前子串的起始位置。
定义一个变量 result，表示最长的子串长度，初始值为 1。
遍历字符串 s，对于每个字符 ch：

Firstly, 如果 ch 在 walkDict 中已经存在，且上一次出现的位置大于等于 begin，则更新 begin 为上一次出现位置的下一个位置，即 begin = walkDict[ch] + 1。

Secondly, 在 walkDict 中记录 ch 的位置 i。

Thirdly, 计算当前子串的长度，即 i - begin + 1，与 result 取最大值，更新 result。

返回 result。

这样就可以使用哈希表来解决这道题目，时间复杂度为 O(n)，其中 n 是字符串 s 的长度。

示意图： 

1
2
3
4
5
6
7
        i  |  0 |  1 |  2 |  3 |  4 |  5 |  6 |  7 |
        -----------------------------------------------
s[i]       |  a |  b |  c |  a |  b |  c |  b |  b |
begin      |  0 |  0 |  0 |  1 |  2 |  3 |  4 |  4 |
result     |  1 |  2 |  3 |  3 |  3 |  3 |  3 |  3 |
walkDict | {a: 0} | {a: 0, b: 1} | {a: 0, b: 1, c: 2} | {a: 3, b: 1, c: 2} | {a: 3, b: 4, c: 2} | {a: 3, b: 4, c: 5} | {a: 3, b: 6, c: 5} | {a: 3, b: 7, c: 5} |

源代码： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
func lengthOfLongestSubstring(_ s: String) -> Int {
    // The border situation, it is important
    if s.isEmpty {
        return 0
    }
    var result = 1 // maximum length of substring without repeating characters
    var begin = 0 // starting index of current substring
    var walkDict = [Character: Int]() // hashtable to store each character's index
    
    for (i, ch) in s.enumerated() { // loop through each character in string s
        if (walkDict[ch] != nil) && walkDict[ch]! >= begin && walkDict[ch]! > -1 { 
            // if current character is already in hashtable and it's index is greater than or equal to the starting index
            // of current substring and not -1, update the starting index of current substring
            begin = walkDict[ch]! + 1
            walkDict[ch] = i // update the hashtable with current character's index
        } else {
            walkDict[ch] = i // add current character's index to hashtable
            result = max(result, i - begin + 1) // update the maximum length of substring without repeating characters
        }
    }
    return result
}