003.无重复字符串的最长子串.md

题目描述

给定一个字符串，请你找出其中不含有重复字符的最长子串的长度。

示例

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

思路

遍历字符串，找到各个无重复的字串。记录重复字符的位置，从重复的位置再开始向后拼接字符串。

解题代码

/**
 * @param  {string} s
 * @return {number}
 */
let lengthOfLongestSubstring = function(s) {
    let subStr = '';
    let maxLength = 0;
    for (let si of s) {
        let index = subStr.indexOf(si)
        if (index === -1) {
            subStr += si;
        } else {
            subStr = subStr.slice(index + 1) + si;
        }
        if (maxLength < subStr.length) {
            maxLength = subStr.length;
        }
    }
    return maxLength;
};

其他优解

/**
 * @param  {string} s
 * @return {number}
 */
let lengthOfLongestSubstring = function(s) {
    if(s === null || s.length === 0){
        return 0;
    }
    // 通过map记录各个重复字符的位置，并在下一次遇到相同字符时更新位置
    let map = {};
    let len = 0;
    let maxLen = len;
    let start = 0;
    for(let i = start, l = s.length; i < l; i++) {
        c = s[i];
        // 有重复字符，并且在当前字串内
        // 当前字串的位置是start->i
        if(map[c] !== undefined && map[c] >= start) {
            start = map[c] + 1;
            len = i - start;
        }
        len++;
        if(len > maxLen){
            maxLen = len;
        }
        map[c] = i;
    }
    return maxLen;
};