Golang/Java 实现无重复字符的最长子串 – LeetCode 算法
给定一个字符串 s ,请你找出其中不含有重复字符的 最长子串 的长度。
来源:力扣(LeetCode)
链接://leetcode-cn.com/problems/longest-substring-without-repeating-characters
示例
示例 1:
输入: s = "abcacadabcd"
输出: 4
解释: 因为无重复字符的最长子串是 "dabc",所以其长度为 3。
示例 2:
输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b",所以其长度为 1。
示例 3:
输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke",所以其长度为 3。
请注意,你的答案必须是 子串 的长度,"pwke" 是一个子序列,不是子串。
示例 4:
输入: s = ""
输出: 0
解题思路
原始字符串:abcacadabcd
Golang 代码实现
func lengthOfLongestSubstring(s string) int {
lastOccurred := make(map[byte]int)
start := 0 // 子串开始的下标
maxLength := 0 // 最大子串长度
for index, ch := range []byte(s) {
// 如果当前字符存在 map 中
//且当前字符的下标在start子串开始位置之后的,如果成立则为发生重复
// 发生重复 start 则当前字符所在的子串下标(map中的下标)后移一位
lastI, ok := lastOccurred[ch]
if ok && lastI >= start {
start = lastI + 1
}
// 计算当前字符下标(index)与 start 下标的距离
distance := index - start + 1
if distance > maxLength {
maxLength = distance
}
// key:当前字符 Ascii 码,value:当前字符下标
lastOccurred[ch] = index
}
return maxLength
}
Java 代码实现
class Solution {
public int lengthOfLongestSubstring(String s) {
int maxLen = 0;
int start = 0;
HashMap<Character, Integer> lastOccurred = new HashMap<>();
char[] chars = s.toCharArray();
int charsLen = chars.length;
for (int i = 0; i < charsLen; i++) {
// 从 map 中获取元素,元素存在且元素出现在start开始的子串中则为重复
Integer lastI = lastOccurred.get(chars[i]);
if (null != lastI && lastI >= start) {
start = lastI + 1;
}
// 计算距离
int distance = i - start + 1;
if (distance > maxLen) {
maxLen = distance;
}
lastOccurred.put(chars[i], i);
}
return maxLen;
}
}