本题难度：★★ 找出一个字符串中最长的连续子串，输出这个子串的长度，要求：这个子串

抛砖一个，模仿 kmp 滑动 <div class="highlight highlight-source-js notranslate position-rela

我同意 <a class="user-mention notranslate" data-hovercard-type="user" data-hovercard-url=

微博上看到的,抛个砖,希望能坚持下去.已经watch <div class="highlight highlight-source-js notranslate p

<div class="highlight highlight-source-js notranslate position-relative overflow-auto" dir="auto" da

<a class="user-mention notranslate" data-hovercard-type="user" data-hovercard-url="/us

Find The Longest Substring about daily-algorithms HOT 7 OPEN

barretlee commented on May 20, 2024

Find The Longest Substring

from daily-algorithms.

Comments (7)

crimx commented on May 20, 2024 1

抛砖一个，模仿 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')

from daily-algorithms.

youngwind commented on May 20, 2024 1

我同意 @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)
}

from daily-algorithms.

tgxpuisb commented on May 20, 2024

微博上看到的,抛个砖,希望能坚持下去.已经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学习

from daily-algorithms.

barretlee commented on May 20, 2024

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 的解法是一样的，应该还有更优解。

from daily-algorithms.

YabZhang commented on May 20, 2024

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

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

进一步优化的，可以使用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

from daily-algorithms.

crimx commented on May 20, 2024

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

from daily-algorithms.

yanqic commented on May 20, 2024

@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}
}

from daily-algorithms.

Find The Longest Substring about daily-algorithms HOT 7 OPEN

Comments (7)

Related Issues (16)

Recommend Projects

React

Vue.js

Typescript

TensorFlow

Django

Laravel

D3

Recommend Topics

javascript

web

server

Machine learning

Visualization

Game

Recommend Org

Facebook

Microsoft

Google

Alibaba

D3

Tencent