最長的子串沒有重複的字符問題與邊緣情況下

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，符合市場預期。