LeetCode#3 Longest Substring Without Repeating Characters

Posted on | Edited on

题目

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

求给定字符串中，不包含重复字符的最长字字符串的长度

此题与 LeetCode#2 Add Two Numbers 一样属于串的算法。解法也类似，使用 map 保存过去的值，对原字符串只遍历一次。关键点在于发现重复字符时回退的计算、index 记录的擦除。

代码

这里给出 golang 的最优解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
func lengthOfLongestSubstring(s string) int {
    m := make(map[byte]int)
    current := 0
    count := 0
    for i := 0; i != len(s); {
        c := s[i]
        if _, ok := m[c]; !ok {
            m[c] = i
            current++
            if (current > count) {
                count = current
            }
            i++
        } else {
            end := m[c]
            m[c] = i
            start := i - current
            
            fmt.Println(start, end)
            for j:= start; j < end; j++ {
                delete(m, s[j])
            }
            fmt.Println(m)
            current = i - end
            i++
        }
        //fmt.Println(i,c)
    }
    return count;
}

上解中，有对 map 的删除操作，假设原字符串实际上长度有限，可以省略掉 map 的删除，进一步空间换时间

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
func lengthOfLongestSubstring(s string) int {
    m := make(map[byte]int)
    current := 0
    count := 0
    for i := 0; i != len(s); {
        c := s[i]
        if existIndex, ok := m[c]; existIndex < i-current || !ok {
            m[c] = i
            current++
            if (current > count) {
                count = current
            }
            i++
        } else {
            end := m[c]
            m[c] = i
            current = i - end
            i++
        }
    }
    return count;
}

此版本运行结果为

Runtime: 8 ms, faster than 84.25% of Go online submissions for Longest Substring Without Repeating Characters.
Memory Usage: 3.1 MB, less than 49.12% of Go online submissions for Longest Substring Without Repeating Characters.

如果极端追求更少的代码行数，可以参考官网解答中给出的 java 解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public class Solution {
    public int lengthOfLongestSubstring(String s) {
        int n = s.length(), ans = 0;
        Map<Character, Integer> map = new HashMap<>(); // current index of character
        // try to extend the range [i, j]
        for (int j = 0, i = 0; j < n; j++) {
            if (map.containsKey(s.charAt(j))) {
                i = Math.max(map.get(s.charAt(j)), i);
            }
            ans = Math.max(ans, j - i + 1);
            map.put(s.charAt(j), j + 1);
        }
        return ans;
    }
}

官网也提供了把原字符串中字符当做 128bit 的 ASCII，使用 bit map 替代 map/hashmap 的解法，应自行斟酌。