最长的子串没有重复的字符问题与边缘情况下

Question

我试图解决这个问题：最长的子字符串不重复的字符。问题是，它在两个测试案例中失败了，我不知道如何解决它。我需要你的帮助，看看我要去哪里错了。

问：

给定一个字符串，找到最长的字符串的长度而不 重复字符。

实例：

鉴于 “abcabcbb”，答案是 “ABC”，其长度为3

鉴于 “BBBBB”，答案为 “b”，具有1的长度。

鉴于“pwwkew”，答案是“wke”，长度为3.请注意， 答案必须是子字符串，“pwke”是子序列，而不是子字符串。

这是我的代码：

function longestSubString(arr){ 
    let localSum=0,globalSum=0; 

    let set = new Set(); 

    for(let i=0; i<arr.length; i++){ 
     let current = arr[i]; 

     //if the key is present in the store. 
     if(set.has(current)){ 
      set.clear(); 
      localSum = 1; 
      set.add(current); 
     } else { 
      localSum +=1; 
      set.add(current); 
     } 

     if(globalSum < localSum){ 
      globalSum = localSum; 
     } 

    } 

    return globalSum; 
} 

测试：

let test = "abcabc"; //returns 3 - correct 
let test2 = "bbb"; //returns 1 - correct 


let test5 = "dvdf"; //returns 2 - INCORRECT! it should return 3 (i.e for vdf) since I'm doing set.clear() I'm not able to store previous elements. 

longestSubString(test5); //incorrect 

直播：

https://repl.it/Jo5Z/10 

Answer 1

未完全测试！

function longestSubString(arr){ 
    let localSum=0,globalSum=0; 

    let set = new Set(); 

    for(let i=0; i<arr.length; i++){ 
     let current = arr[i]; 

     //if the key is present in the store. 
     if(set.has(current)){ 
      let a = Array.from(set); 
      a.splice(0,a.indexOf(current)+1); 
      set = new Set(a); 
      set.add(current); 
      localSum = set.size; 
     } else { 
      localSum +=1; 
      set.add(current); 
     } 

     if(globalSum < localSum){ 
      globalSum = localSum; 
     } 

    } 

    return globalSum; 
} 

的想法是，当你重复的，你应该从charachter第一复制字符后开始，你的情况dvdf，当你到达第二个d你应该从vd不会继续从d！

Answer 2

你必须考虑子字符串可能从字符串中的任何字符开始。仅在找到重复项时才擦除集合，这使得您只考虑从等于第一个字符的字符开始的子字符串。

的O（LOGN * N^2）溶液修改你只是有点：

function longestSubString(arr){ 
    let globalSum=0; 

    for(let i=0; i<arr.length; i++){ 
     let set = new Set(); 
     let localSum=0; 
     for(let j=i; j<arr.lenght; j++){   

      let current = arr[j]; 

      //if the key is present in the store. 
      if(set.has(current)){ 
       break; 
      } else { 
       localSum +=1; 
       set.add(current); 
      } 
     } 
     if(globalSum < localSum){ 
      globalSum = localSum; 
     } 
    } 

    return globalSum; 
} 

还有一个为O（n + d）（几乎线性）溶液，d是字符数在字母。见http://www.geeksforgeeks.org/length-of-the-longest-substring-without-repeating-characters/。

Answer 3

下面的解决方案得到长度O(n+d)时间，还打印最长的非重复字符子和：

public void longestNonRepeatingLength(String a){ 
     a="dvdf"; 
     int visitedIndex[] = new int[256]; 
    int curr_len = 0, max_len = 0, prev_ind = 0, start = 0, end = 1; 
    for(int i =0;i<256;i++) 
     visitedIndex[i] = -1; 
    visitedIndex[a.charAt(0)] = 0; 
    curr_len++; 
    int i = 0; 
    for(i=1;i<a.length();i++){ 
     prev_ind = visitedIndex[a.charAt(i)]; 
     if(prev_ind == -1 || i > prev_ind + curr_len) 
      curr_len++; 
     else{ 
      if(curr_len>max_len){ 
           start = prev_ind + 1; 
           end = i; 
           max_len = curr_len; 
          } 

      curr_len = i - prev_ind; 

     } 
     visitedIndex[a.charAt(i)] = i; 
    } 
      if(curr_len>max_len){ 
           end = i-1; 
           max_len = curr_len; 
          } 
    for(i = start;i<=end;i++) 
     System.out.print(a.charAt(i)); 
    System.out.println(""); 
    System.out.println("Length = "+max_len); 
} 

Answer 4

由于set包含了最大的一套关于指数i结尾的字符串的非重复字符，这意味着当你遇到一个以前看过的角色时，而不是像现在你的代码那样从一个空集合开始，你应该从你的集合中删除所有的字符，直到重复一个。

举例来说，您的输入是"abXcXdef"。遇到第二个"X"时，您会想要从您的设置中删除"a"和"b"，并将一组("c","X")设置为该时间点的最长设置。将所有其他字符（如无是重复的），然后你会得到5

像这样的最大长度最终应该工作：

function longestSubString(arr) { 
    let globalSum = 0; 
    let set = new Set(); 
    for (let i=0; i<arr.length; i++) { 
     let current = arr[i]; 
     if (set.has(current)) { 
      while (true) { 
       let removeChar = arr[i - set.count]; 
       if (removeChar != current) 
        set.remove(removeChar); 
       else 
        break; 
      } 
     } else { 
      set.add(current); 
      if (set.count > globalSum) 
       globalSum = set.count; 
     } 
    } 
    return globalSum; 
} 

由于每个字符添加最多一次，并删除最多一次，这是一个O（N）算法。

Answer 5

这里似乎有很多很长的答案。我想到的实现由于两种观察而被简化：

• 无论何时遇到重复字符，都需要在当前字符的前一次出现之后开始下一个子字符串。
• Set()重复时按照插入顺序创建数组。

function longestSubstring(str) { 
 
    let maxLength = 0 
 
    let current = new Set() 
 

 
    for (const character of str) { 
 
    if (current.has(character)) { 
 
     const substr = Array.from(current) 
 

 
     maxLength = Math.max(maxLength, substr.length) 
 
     current = new Set(substr.slice(substr.indexOf(character) + 1)) 
 
    } 
 

 
    current.add(character) 
 
    } 
 

 
    return Math.max(maxLength, current.size) 
 
} 
 

 
const tests = [ 
 
    "abcabc", 
 
    "bbb", 
 
    "pwwkew", 
 
    "geeksforgeeks", 
 
    "dvdf" 
 
] 
 

 
tests.map(longestSubstring).forEach(result => console.log(result))

一个简单的编辑使我们能够保持最大的子串，而不是最长的一次出现。

function longestSubstring(str) { 
 
    let maxSubstr = [] 
 
    let current = new Set() 
 

 
    for (const character of str) { 
 
    if (current.has(character)) { 
 
     const substr = Array.from(current) 
 

 
     maxSubstr = maxSubstr.length < substr.length ? substr: maxSubstr 
 
     current = new Set(substr.slice(substr.indexOf(character) + 1)) 
 
    } 
 

 
    current.add(character) 
 
    } 
 

 
    const substr = maxSubstr.length < current.size ? Array.from(current) : maxSubstr 
 

 
    return substr.join('') 
 
} 
 

 
const tests = [ 
 
    "abcabc", 
 
    "bbb", 
 
    "pwwkew", 
 
    "geeksforgeeks", 
 
    "dvdf" 
 
] 
 

 
tests.map(longestSubstring).forEach(result => console.log(result))

正如我们所看到的，最后的测试产量vdf，符合市场预期。