剑指 Offer 48. 最长不含重复字符的子字符串

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

示例 1:

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

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

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

提示：

s.length <= 40000

方法一：双指针+Map（哈希表）

/**
 * @param {string} s
 * @return {number}
 */
 // 双指针+Map(哈希表)
var lengthOfLongestSubstring = function(s) {
    let i = -1 ;
    let res = 0;
    let hashMap = new Map()
    for(let j=0;j<s.length;j++){
        if(hashMap.has(s.charAt(j))){
            i = Math.max(i,hashMap.get(s.charAt(j)))
        }
        hashMap.set(s.charAt(j),j)
        res = Math.max(res,j-i)
    }
    return res
};

方法二：动态规划 + 哈希表

/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function(s) {
    let tmp = 0;
    let res = 0;
    let hashMap = new Map()
    for(let i = -1, j= 0;j<s.length;j++){
        if(hashMap.has(s.charAt(j))){
            i = Math.max(i,hashMap.get(s.charAt(j)))
        }
        hashMap.set(s.charAt(j),j)
        tmp = tmp<j-i?tmp+1:j-i // dp[j - 1] -> dp[j]
        res = Math.max(res,tmp) // max(dp[j - 1], dp[j])
    }
    return res
};

方法三：动态规划+线性遍历

/**
 * @param {string} s
 * @return {number}
 */
 //动态规划+线性遍历
var lengthOfLongestSubstring = function(s) {
    let tmp = 0;
    let res = 0;
    for(let j = 0;j<s.length;j++){
        let i= j-1;
        while(i>=0&&s.charAt(i)!=s.charAt(j))i--
        tmp = tmp<j-i?tmp+1:j-i // dp[j - 1] -> dp[j]
        res = Math.max(res,tmp) // max(dp[j - 1], dp[j])
    }
    return res
};