请问在一个字符串中找一个不重覆且最长或者最短的的字符串的最好方法是什么（ JavaScript）？

[83f420984]

在 LeetCode 上做字符处理的题目时，一般我用两个 for 套在一起循环遍历，最后要么超时，要么时间太长了，一直没找到特别好的方法，请问在处理这一类问题时有什么特别好的解法吗？

比如下面的题目：

https://leetcode.com/problems/longest-substring-without-repeating-characters

https://leetcode.com/problems/longest-palindromic-substring/#/description

[Ariver]

https://discuss.leetcode.com/topic/8232/11-line-simple-java-solution-o-n-with-explanation

[Arrowing]

982 / 983 test cases passed.
最后一个超时了，T_T。。。

[Chrisplus]

双向队列，O(N)的时间复杂度？

[wayne712]

Longest Palindromic Substring 一点思路，
利用两个下标，如 i, j
假设输入"babad",
i 不断向左边走，j 不断向右边走， 即两个下标 i 递减，j 递增
在这过程中判断两个下标所在字符是否相等， 相等则继续下一对下标的比较，
否则就中断循环，通过 substring，得到 i 和 j 之间的字符串。

最坏的时间复杂度是 O(n^2)
文字不太会表达，希望有帮助

[Magic347]

public class Solution {
　　 public int lengthOfLongestSubstring(String s) {
　　 　　 if (s == null || s.length() <= 0) {
　　 return 0;
　　 }
　　 int[] visited = new int[256];
　　 for (int i = 0; i < 256; i++) {
　　 visited[i] = -1;
　　 }
　　 int start = 0;
　　 int end = 0;
　　 int len = s.length();
　　 int retval = 1;
　　 while (end < len) {
　　 char ch = s.charAt(end);
　　 if (visited[ch] >= 0) {
　　 // current char is visited so far
　　 int currLen = end - start;
　　 if (currLen > retval) {
　　 retval = currLen;
　　 }
　　 int k = visited[ch];
　　 for (int i = start; i <= k; i++) {
　　 visited[s.charAt(i)] = -1;
　　 }
　　 start = k + 1;
　　 } else {
　　 // current char is not visited so far
　　 if (end == len - 1) {
　　 // reach the end of the string
　　 　　 int currLen = end - start + 1;
　　 　　 if (currLen > retval) {
　　 　　 retval = currLen;
　　 　　 }
　　 　　 }
　　 }
　　 visited[ch] = end;
　　 end ++;
　　 }
　　 return retval;　　 　　
　　 }
}

[Magic347]

O(n)
https://leetcode.com/problems/longest-substring-without-repeating-characters

public class Solution {　　
　　 public int lengthOfLongestSubstring(String s) {
　　　　 if (s == null || s.length() <= 0) {
　　　　　　 return 0;
　　　　}
　　　　 int[] visited = new int[256];
　　　　 for (int i = 0; i < 256; i++) {
　　　　　　 visited[i] = -1;
　　　　}
　　　　 int start = 0;
　　　　 int end = 0;
　　　　 int len = s.length();
　　　　 int retval = 1;
　　　　 while (end < len) {
　　　　　　 char ch = s.charAt(end);
　　　　　　 if (visited[ch] >= 0) {
　　　　　　　　// current char is visited so far
　　　　　　　　 int currLen = end - start;
　　　　　　　　 if (currLen > retval) {
　　　　　　　　　　 retval = currLen;
　　　　　　　　}
　　　　　　　　 int k = visited[ch];
　　　　　　　　 for (int i = start; i <= k; i++) {
　　　　　　　　　　 visited[s.charAt(i)] = -1;
　　　　　　　　}
　　　　　　　　 start = k + 1;
　　　　　　} else {
　　　　　　　　// current char is not visited so far
　　　　　　　　 if (end == len - 1) {
　　　　　　　　　　// reach the end of the string
　　　　　　　　　　 int currLen = end - start + 1;
　　　　　　　　　　 if (currLen > retval) {
　　　　　　　　　　　　 retval = currLen;
　　　　　　　　　　}
　　　　　　　　}
　　　　　　}
　　　　　　 visited[ch] = end;
　　　　　　 end ++;
　　　　}
　　　　 return retval;
　　}
}

[YuJianrong]

这种题目时间不是 O （ n ）都肯定不对的，即使过了不过是 case 不好。

[Arrowing]

终于做出来了，之前思路错了。
983 / 983 test cases passed. Status: Accepted Runtime: 155 ms
You are here! Your runtime beats 98.17 % of javascript submissions.

```javascript
/**
* @param {string} s
* @return {number}
*/
var lengthOfLongestSubstring = function(s) {
var sLen = s.length,
maxLen = 0,
maxStr = '',
tmpStr,
posIndex,
i;

for( i = 0 ; i < sLen; i++ ){

tmpStr = s[i];
posIndex = maxStr.indexOf(tmpStr);

if(posIndex > -1){
maxStr = maxStr.substring(posIndex + 1);
}

maxStr += tmpStr;
maxLen = Math.max(maxLen, maxStr.length);
}

return maxLen;
};
```

[momocraft]

题目有点歧义，叫"最长不含重复子串"可能更好？"最长不重复子串"是另一个问题。

[YuJianrong]

这样还是不行的，这是 O(m*n)复杂度，m 是 character 种类。你应该想想怎么做到 O(n)。
提示 hashmap 的添加和查询我们一般认为是 O(1)的

[mengzhuo]

就是滑动窗口嘛~~87% AC 路过

```
func lengthOfLongestSubstring(s string) int {
var dict [256]int
for i:=0;i<256;i++{
dict[i] = -1
}
start := -1
maxLen := 0
for i, c := range []byte(s) {
if dict[uint8(c)] > start {
start = dict[uint8(c)]
}
dict[uint8(c)] = i
maxLen = max(i - start, maxLen)
}
return maxLen
}

func max(a,b int) int{
if a > b {
return a
}
return b
}
```

[yuann72]

983 / 983 test cases passed.
Status: Accepted
Runtime: 158 ms (这 Runtime 一会长的时候 190+ 短的时候 157+)
Submitted: 0 minutes ago


/**
* @param {string} s
* @return {number}
*/
var lengthOfLongestSubstring = function(s){
var subStrs = [],
curSubStr = '',
i=0,len=s.length;
for(;i<len;i++){
if(!curSubStr.includes(s[i])){
curSubStr += s[i];
}else{
subStrs.push(curSubStr);
curSubStr = curSubStr.slice(curSubStr.indexOf(s[i]) + 1) + s[i];
}
}
subStrs.push(curSubStr);
for(i=0,len=subStrs.length;i<len;i++){
if (subStrs[i].length > curSubStr.length) {
curSubStr = subStrs[i];
}
}
return curSubStr.length;
};