Find The Longest Substring

[barretlee]

本题难度：★★

找出一个字符串中最长的连续子串，输出这个子串的长度，要求：这个子串中没有重复的字符。

比如：

给定 abcabcbb，最长的子串为 abc，那么输出结果为 3;
给定 bbbbb，最长的子串是 b，输出结果为 1;
给定 pwwkew，最长的子串为 wke，输出 3.

参考答案：https://github.com/barretlee/daily-algorithms/blob/master/answers/4.md

[crimx]

抛砖一个，模仿 kmp 滑动

function longestUniqueSubstr (str) {
  str = String(str)

  var index = {} // keys: char of a tentative substr, values: index
  var tenLen = 0 // len of the tentative substr

  var resLen = 0 // result len

  for (let i = 0; i < str.length; i += 1) {
    let ic = index[str[i]]
    if (typeof ic !== 'undefined') {
      if (tenLen > resLen) { resLen = tenLen }
      i = ic + 1
      index = {}
      tenLen = 0
    }
    index[str[i]] = i
    tenLen += 1
  }

  return Math.max(tenLen, resLen)
}

console.assert(longestUniqueSubstr('abcabcbb') === 3, 'abcabcbb')
console.assert(longestUniqueSubstr('bbbbb') === 1, 'bbbbb')
console.assert(longestUniqueSubstr('pwwkew') === 3, 'pwwkew')
console.assert(longestUniqueSubstr('') === 0, '')
console.assert(longestUniqueSubstr('1') === 1, '1')
console.assert(longestUniqueSubstr('111') === 1, '111')
console.assert(longestUniqueSubstr('1234') === 4, '1234')
console.assert(longestUniqueSubstr('11234') === 4, '11234')
console.assert(longestUniqueSubstr('12344') === 4, '12344')
console.assert(longestUniqueSubstr('1234445678') === 5, '1234445678')
console.assert(longestUniqueSubstr('1234235678') === 7, '1234235678')

[tgxpuisb]

微博上看到的,抛个砖,希望能坚持下去.已经watch

function test(str) {
	let map = {}
	let currentLen = 0
	let result = 0
	for (let i = 0; i < str.length; i++) {
		if (map[str[i]] === undefined) {
			currentLen++
			map[str[i]] = i
		} else {
			if (currentLen > result) {
				result = currentLen
			}
			currentLen = 0
			i = map[str[i]]
			map = {}
		}
	}
	return Math.max(currentLen, result)
}

写完之后才发现楼上的更好,更简洁,向楼上crimx学习

[barretlee]

console.assert(resolve('abbcdefdakngda') === 7);

function resolve(str) {
  let maxLen = 0;
  let map = {
    length: 0
  };
  for(let i = 0, len = str.length; i < len; i++) {
    if (map[str[i]]) {
      maxLen = Math.max(map.length, maxLen);
      i = map[str[i]] + 1;
      map = {};
      map.length = 0;
    }
    map[str[i]] = i;
    map.length++;
  }
  return Math.max(map.length, maxLen);
}

写了一个，发现与 @crimx 的解法是一样的，应该还有更优解。

[YabZhang]

题目：找出一个字符串中最长的连续子串，输出这个子串的长度，要求：这个子串中没有重复的字符。
那么重点就在"没有重复字符"。

最简单的思路就是暴力遍历法，并在遍历的同时统计长度，找到重复字符就停止。最后给出最大的长度。

进一步优化的，可以使用hash表记录下来每个元素出现的索引值；
使用hash表记录，并在每次发现重复元素重新开始统计时，并从重复元素第一次出现的下一位继续算法；

进一步优化，重用建立的hash记录，每次发现重复元素时进行更新；
具体的思路就是用最新出现的元素索引覆盖之前出现的，并对当前的长度进行更新；
这样可以保证时间复杂度最坏：O(n)，空间复杂度为：O(n)

代码如下：

def resolve(seq):
    stat = {}
    index = 0
    max_len, tmp_len = 0, 0
    while(index < len(seq)):
        if seq[index] not in stat:
            tmp_len += 1
        else:
            if tmp_len > max_len:
                max_len = tmp_len
            tmp_len = index - stat[seq[index]]
        # update stat record
        stat[seq[index]] = index
        index += 1
    return max(max_len, tmp_len)

assert resolve('abcabcbb') == 3
assert resolve('bbbb') == 1
assert resolve('pwwkew') == 3
assert resolve('1') == 1
assert resolve('111') == 1
assert resolve('112345678') == 8

[youngwind]

我同意 @YabZhang 的算法， @crimx 的算法并非最优。
以 "abcabcbb" 为例，crimx 的算法 for 循环执行了 15 次，而 YabZhang 的 for 循环只执行了 8 次，YabZhang 的算法真正地做到了在任何情况下时间复杂度都是 O(n)。
crimx 的算法只有在某些情况才能达到 O(n)，如"11234"，"2223445"，也就是”相同的元素必须相邻“。
为什么会这样呢？我觉得问题在于 crimx 的算法中 i 指针进行了回溯，如下图所示。

举个例子："abca"，之前已经判断出 "abc" 是最大非重复子串。那么，再碰到第 4 位的相同元素 "a"，因为第 4 位和第 1 为相同，1、2、3位构成最大非重复子串，那么2、3、4位自然也构成最大非重复子串。这个结论是可以直接推导出来的，不需要重复遍历 "bca" 才能知道。然而 crimx 的算法进行了这种冗余的遍历，我觉得这是 YabZhang 算法优于 crimx 算法的根本原因。
下面我把 YabZhang 的算法翻译成 JS 版本，以供测试。

function test(str) {
    var index = {} // keys: char of a tentative substr, values: index
    var tenLen = 0 // len of the tentative substr

    var resLen = 0 // result len

    for (let i = 0; i < str.length; i += 1) {
        let ic = index[str[i]]
        if (typeof ic !== 'undefined') {
            if (tenLen > resLen) {
                resLen = tenLen
            }
            tenLen = i - ic;
            index[str[i]] = i;
        } else {
            tenLen += 1;
        }
        index[str[i]] = i
    }

    return Math.max(tenLen, resLen)
}

[crimx]

@youngwind 确实记录每个字符最新的位置就不需要回溯了:thumbsup: 这样就保证了 i 到 ic 之间的字符必然是独立的。

[yanqic]

@youngwind ，你算法有问题console.log(test('abccdefab')) 输出 7。计算速度1.4s
下面是我的笨方法，但是计算速度0.8s；
function longSubstr(str) {
var index ='';var length=0;var nstr=0;var longstr='';
for(var i = 0;i<str.length;i++){
if(index.indexOf(str[i])>-1){
index = '';
i=nstr;
nstr++;
} else {
index = index + str.charAt(i);
if(length<index.length){
length= index.length
longstr = index;
}
}
}
return {str: longstr, length: length}
}