Longest Substring Without Repeat

分析

本题最理想的状态是只遍历一遍字符串，为了在遍历的时候确定有无重复的字符，我们需要一个哈希表 hash 辅助查询，javascript 中的对象可以充当哈希表的角色，键是某一个字符，值为该字符在字符串中的位置。

在遍历的时候设置一个变量 head 指向子串的头，一个变量 tail 指向子串的尾，每次将 tail 的位置向后移一位，在哈希表中查询 tail 位置处的新字符，以 hash 中有无新字符来决定下一步的操作。

想象一下，由于我们是通过 tail 来遍历字符串的，tail 的更新方式是每次都会 +1 直到遍历完字符串为止；同时，对于 hash 的更新，我们在遍历字符的过程中不停往 hash 中添加新的 { 字符: 字符在字符串中的位置 } 或者覆盖已有字符的位置；那么 head 呢，head 是怎样更新它的值的？

head 的值是根据 tail 在遍历到新字符的时候 hash 中是否已经存在该字符的情况来决定：

1. 如果不存在，说明当前子串是没有重复字符的子串，head 的位置无需变动

2. 如果存在，就以 hash 中的重复字符在字符串中的位置与当前 head 的位置之间的相对位置关系来进行处理：

• 重复字符位于 head 之前的，head 值是无需更新的
• 重复字符位于 head 与 tail 之间的，head 值更新为重复字符的下一位

最后，对于子串的最长长度 count，显然其值为 tail-head+1，在每次遍历字符的时候对它进行更新即可。

解答

代码如下：

var lengthOfLongestSubstring = function(s) {
    if ( Object.prototype.toString.call(s) !== "[object String]" ) return;

    var head = 0,
        tail = 0,
        len = s.length,
        count = 0,
        hash = {};

    for ( ;tail < len; tail ++ ) {
        if (hash[s.charAt(tail)] !== undefined) {
            head = Math.max(hash[s.charAt(tail)] + 1, head);
        }
        count = Math.max(count, tail - head + 1);
        hash[s.charAt(tail)] = tail;
    }

    return count;
};