Longest Substring Without Repeating Characters (M)
题目
Given a string, find the length of the longest substring without repeating characters.
Example 1:
Input: "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.
Example 2:
Input: "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.
Example 3:
Input: "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3.
Note that the answer must be a substring, "pwke" is a subsequence and not a substring.
题意
给定一个字符串，找到一个子串，使得子串内没有重复的字符，求该子串的最大长度。
思路
普通解法直接暴力三重循环(O(N^3))。
较优解法是使用一个“可伸缩”的数组框在字符串上滑动，先向右移动右端点，判断右端点的字符在不在被“伸缩数组”框住的子串中，如果重复则不断向右移动左端点，直到将重复的字符排除在“伸缩数组”外。这样相当于字符串中的每一个字符都要走一遍，复杂度(O(2N) = O(N))。
对上述方法的一个优化是，用一个数组记录字符串中每一个字符对应的索引位置，这样在右端点字符重复时，左端点可以直接跳到子串中字符重复的地方，不需要一步一步向右移动左端点。这样只需要右端点走一遍字符串即可，复杂度直接为(O(N))。
代码实现
Java
Set
class Solution {
public int lengthOfLongestSubstring(String s) {
int left = 0;
// right指向子串的右边一个字符
int right = 0;
int maxLen = 0;
Set<Character> set = new HashSet<>();
while (right < s.length()) {
if (set.contains(s.charAt(right))) {
set.remove(s.charAt(left++));
} else {
set.add(s.charAt(right++));
maxLen = Math.max(right - left, maxLen);
}
}
return maxLen;
}
}
Hash优化
class Solution {
public int lengthOfLongestSubstring(String s) {
int left = 0;
// right指向子串的最后一个字符
int right = 0;
int maxLen = 0;
// 下标记录字符，值记录该字符在字符串中对应的索引+1
// 实际上记录的是左端点应该跳转到的位置
int[] hash = new int[128];
while (right < s.length()) {
left = Math.max(left, hash[s.charAt(right)]);
maxLen = Math.max(maxLen, right - left + 1);
hash[s.charAt(right)] = ++right;
}
return maxLen;
}
}
JavaScript
Set
/**
* @param {string} s
* @return {number}
*/
var lengthOfLongestSubstring = function (s) {
let left = 0
let right = 0
let max = 0
let set = new Set()
while (right < s.length) {
if (set.has(s[right])) {
set.delete(s[left++])
} else {
set.add(s[right++])
max = Math.max(right - left, max)
}
}
return max
}
Hash优化
/**
* @param {string} s
* @return {number}
*/
var lengthOfLongestSubstring = function (s) {
let left = 0
let right = 0
let max = 0
let hash = new Map()
while (right < s.length) {
let index = hash.get(s[right]) !== undefined ? hash.get(s[right]) : -1
left = Math.max(left, index + 1)
max = Math.max(max, right - left + 1)
hash.set(s[right], right++)
}
return max
}