剑指offer面试题48：最长不含重复字符的子字符串（golang实现）

题目描述

请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。

示例1：

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

示例2

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

示例3

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

提示

s.length <= 40000

算法分析

用一个map（哈希实现）记录字符串中出现过的字符（key为该字符，value为该字符上次出现的位置），start记录当前不含重复字符的子字符串起点。对于第i个字符来说，若

• 第i个字符之前未出现过，当前字符串长度加一，在map中将prevIndex替换为i
• 第i个字符之前出现过，在map中查找到第i个字符最近一次出现的位置prevIndex，start = prevIndex + 1；cur等于 i - prevIndex + 1；并且在map中将prevIndex替换为i

复杂度分析

问题规模为字符串长度n

• 时间复杂度：O(n)，需要遍历一遍字符串
• 空间复杂度：O(1)，map长度小于等于ASCII码范围，可看做常数

Golang代码如下

func lengthOfLongestSubstring(s string) (max int) {
	m := make(map[byte]int)
	start, cur := 0, 0
	for k, v := range s {
		if _, ok := m[byte(v)]; !ok {
			m[byte(v)] = k
			cur++
		} else {
			if start > m[byte(v)] {
				m[byte(v)] = k
				cur++
			} else {
				cur = k - m[byte(v)]
				start = m[byte(v)] + 1
				m[byte(v)] = k
			}
		}
		if max < cur {
			max = cur
		}
	}
	return
}