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

解题思路：

滑动窗口法

1. 当前字符在窗口中的索引为index
2. 若当前字符在窗口中出现过，那么就将窗口中[0,index]区间的全部去除，从index+1开始新一轮的窗口
3. 当前字符加入窗口
4. 更新最大值

（indexOf谨慎用）

代码1：

const lengthOfLongestSubstring = s => {
    // 滑动窗口
    const window = [];
    let max = 0;
    const len = s.length;
    for (let i = 0; i < len; i++) {
        // 当前字符在窗口中的索引
        const index = window.indexOf(s[i]);
        if (index !== -1) {
            // 当前字符在窗口中出现过，那么就将窗口中[0,index]区间的全部去除
            // 从index+1开始新一轮的窗口
            window.splice(0, index + 1);
        }
        // 当前字符加入窗口
        window.push(s[i]);
        // 更新最大值
        if (max < window.length) max = window.length;
    }
    return max;
};

代码2：

const lengthOfLongestSubstring = s => {
    let start=0,max=0
    let res=new Set()
    for(var end=0;end<s.length;end++){
        if(!res.has(s[end])){
            res.add(s[end])
        }else{
            max=Math.max(end-start,max)
            while(res.has(s[end])){
                res.delete(s[start])
                start++
            }
            res.add(s[end])
        }
    }
    max=Math.max(end-start,max)
    return max
};

最长连续子字符串

解题思路：

连续子字符串跟不重复的不一样！！！！直接动态规划遍历存储！不要给相同的思路束缚了，踩坑了（一直debug发现想复杂了！T T），动态规划真香。。。。。。

踩坑代码：

function findLongestSubstr( str ) {
    // write code here
    let start=0,max=0
    let res=[]
    let i=0,j=0
    if(str.length<=1)return str
    str=str.split('')
    for(var end=0;end<str.length;end++){
       
        if(res.indexOf(str[end])!=-1||res.indexOf(str[end].toLowerCase())!=-1||res.indexOf(str[end].toUpperCase())!=-1){
            res.push(str[end])
        }else{
           res.push(str[end])
                
           if(end-start>max){
               max=end-start
               i=end  
               j=start
               res.splice(0,max)
           }         
            start=end
           
        }
    }
   
    return str.slice(j,i).join('')
}

踩坑报错情况：

都9/11了！！！恶心吐了！！！！干嘛要想这么复杂啊我透！

代码：

function findLongestSubstr( str ) {
    if(!str) return ""
    let max=str[0]
    let dp=[]
    dp[0]=1
    for(let i=1;i<str.length;i++){
        if(str[i-1].toLowerCase()==str[i].toLowerCase()){
            dp[i]=dp[i-1]+1
        }else{
            dp[i]=1
        }
        max=dp[i]>max.length?str.slice(i+1-dp[i],i+1):max
    }
    return max
}
module.exports = {
    findLongestSubstr : findLongestSubstr
};