Leaky Cauldron
0%

无重复字符的最长子串

Posted on Edited on

题目(LeetCode #3)

给定一个字符串，请你找出其中不含有重复字符的最长子串的长度。

示例 1:

输入: “abcabcbb”
输出: 3
解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。

示例 2:

输入: “bbbbb”
输出: 1
解释: 因为无重复字符的最长子串是 “b”，所以其长度为 1。

示例 3:

输入: “pwwkew”
输出: 3
解释: 因为无重复字符的最长子串是 “wke”，所以其长度为 3。答案必须是子串的长度，”pwke” 是一个子序列，不是子串。

题解

可采用滑动窗口法，将窗口内的字符保存到集合中，窗口的左边界向右移动时，弹出已不在窗口内的元素；窗口的右边界向右移动时判断字符是否已在集合中，若不在则加入，若已有则终止循环，记录当前最长长度。

Java

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
import java.util.HashSet;

public class Solution {
    public int lengthOfLongestSubstring(String s) {
        HashSet<Character> charSet = new HashSet<>();
        int length = s.length();
        int rk = -1, ans = 0;

        for (int i = 0; i < length; i++) {
            if (i != 0) {
                charSet.remove(s.charAt(i - 1));
            }
            while (rk + 1 < length && !charSet.contains(s.charAt(rk + 1))) {
                charSet.add(s.charAt(rk + 1));
                rk++;
            }
            ans = Math.max(ans, rk - i + 1);
        }

        return ans;
    }

    public static void main(String[] args) {
        String s = "abcabcbb";
        Solution solution = new Solution();
        System.out.println(solution.lengthOfLongestSubstring(s));
    }
}

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        char_set = set()
        rk, ans = -1, 0
        length = len(s)

        for i in range(length):
            if i != 0: char_set.remove(s[i - 1])

            while rk + 1 < length and s[rk + 1] not in char_set:
                char_set.add(s[rk + 1])
                rk += 1
            ans = max(ans, rk - i + 1)

        return ans

Go

Golang 中没有集合，使用 map 实现过于繁琐，可采用 int 数组来模拟集合操作。

将每个字符的 ASCII 值作为数组的索引，数组内存储的为该字符的出现与否（1 或 0）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
package main

import (
	"fmt"
	"math"
)

func lengthOfLongestSubstring(s string) int {
	var window [128]int         // ASCII 总共定义了 128 个字符
	length := len(s)
	rk, ans := -1, 0

	for i, _ := range s {
		if i != 0 {
			window[s[i-1]] = 0  // 左边界移出窗口
		}
		for rk+1 < length && window[s[rk+1]] == 0 {
			window[s[rk+1]] = 1 // 右边界移入窗口
			rk++
		}
		ans = int(math.Max(float64(ans), float64(rk-i+1)))
	}
	return ans
}