Java程式查詢最長無重複字元子字串的長度

---

在Java中，子字串是字串的一部分，包含字串中任意長度（從1到整個字串）的連續字元。給定一個字串，我們需要找到該字串中僅包含唯一字元的最長子字串的長度。我們將看到三種方法：查詢每個子字串、滑動視窗和雙指標。

問題陳述

給定一個字串，編寫一個Java程式來查詢最長無重複字元子字串的長度 -

輸入

thisisthegivenstring

輸出

The length of the longest substring that contains only unique characters is: 8

查詢最長無重複字元子字串的方法

• 查詢每個子字串
• 滑動視窗
• 雙指標

方法1：查詢每個子字串

在這種方法中，我們將獲取每個子字串，然後檢查是否存在任何重複字元。以下是步驟 -

• 定義一個函式isUnique來檢查子字串是否包含唯一字元。
• 使用布林陣列標記非唯一字元。
• 遍歷子字串並檢查重複字元。
• 如果沒有重複，則返回true。
• 定義另一個函式longestSubStr來查詢包含唯一字元的最長子字串。
• 遍歷字串並獲取每個子字串。
• 對每個子字串呼叫isUnique並更新最大長度。
• 返回最大長度。

示例

public class Solution{
   // function to check the unique characters 
   public static boolean isUnique(String str, int i, int j){
      // array to store the non-unique characters 
      boolean arr[] = new boolean[26];        
      // traversing over the string 
      while(i <= j){
         if(arr[str.charAt(i)-'a'] == true){
            return false; // returning false as answer 
         }
         else{
            arr[str.charAt(i)-'a'] = true;
         }
         i++;
      }
      return true; // returning true 
   }    
   // function to get the required substring 
   public static int longestSubStr(String str){
      int len = str.length();  
      int ans = 0; // variable to store the answer         
      // traversing over the string 
      for(int i=0; i<len; i++){            
         // function to get every substring starting from here
         for(int j = i; j<len; j++){                
            // calling function to check if the current substring contains the unique characters 
            if(isUnique(str, i,j)){
               ans = Math.max(ans, j-i+1);
            }
         }
      }
      return ans; // return the final answer 
   }    
   // main function 
   public static void main(String []args){
   String str = "thisisthegivenstring"; // given string     
   // calling to the function 
   int ans = longestSubStr(str);    
   // print the final answer 
   System.out.println("The length of the longest substring that contains only unique characters is: " + ans );
   }
}

輸出

The length of the longest substring that contains only unique characters is: 8

時間和空間複雜度

以上程式碼的時間複雜度為O(N^3)，其中N是給定字串的長度。

以上程式碼的空間複雜度為常數或O(1)，因為我們在這裡沒有使用任何額外的空間。

方法2：滑動視窗

在這種方法中，我們將使用指標建立一個視窗，並遍歷字串，直到視窗不包含任何重複字元。以下是步驟 -

• 定義一個函式longestSubStr來查詢包含唯一字元的最長子字串。
• 使用for迴圈遍歷從索引i到len 的字串str。
• 建立一個布林陣列arr來儲存非唯一字元。
• 初始化兩個指標i和j到視窗的開頭。
• 透過向右移動j來擴充套件視窗。
• 如果找到重複字元，則中斷迴圈並向右移動i。
• 如果當前視窗包含唯一字元，則更新最大長度ans。
• 重複步驟5-7，直到到達字串的末尾。
• 返回最大長度ans。

示例

public class Solution{    
   // function to get the required substring 
   public static int longestSubStr(String str){
      int len = str.length(); 
      int ans = 0; // variable to store the answer         
      // traversing over the string 
      for(int i=0; i<len; i++){            
         // array to store the non-unique characters 
         boolean arr[] = new boolean[26];            
         // function to get every substring starting from here
         for(int j = i; j<len; j++){
            if(arr[str.charAt(j)-'a'] == true){
               break;
            }
            else{
               arr[str.charAt(j)-'a'] = true;
               ans = Math.max(ans,j-i+1);
            }
         }
      }
      return ans; // return the final answer 
   }    
   // main function 
   public static void main(String []args){
   String str = "thisisthegivenstring"; // given string 
    
   // calling to the function 
   int ans = longestSubStr(str);    
   // print the final answer 
   System.out.println("The length of the longest substring that contains only unique characters is: " + ans );
   }
}

輸出

The length of the longest substring that contains only unique characters is: 8

時間和空間複雜度

以上程式碼的時間複雜度為O(N^2)，其中N是給定字串的長度。

以上程式碼的空間複雜度為常數或O(1)，因為我們在這裡沒有使用任何額外的空間。

方法3：雙指標

在這種方法中，我們將使用雙指標的概念，一個指標緩慢移動，另一個指標快速移動，並將慢指標更新到先前出現當前字元的索引處。以下是步驟 -

• 定義一個函式longestSubStr來查詢包含唯一字元的最長子字串。
• 初始化一個數組arr來儲存每個字元的最後一個索引。
• 將陣列填充為-1。
• 初始化兩個指標i（慢）和j（快）為0。
• 使用快指標 j遍歷字串str。
• 將慢指標i更新為其當前值和當前字元的最後一個索引+1中的最大值。
• 將答案ans更新為其當前值和當前子字串的長度（j - i + 1）中的最大值。
• 在陣列arr中更新當前字元的最後一個索引。
• 重複步驟5-8，直到到達字串的末尾。
• 返回答案ans。

示例

import java.util.*; 
public class Solution{    
   // function to get the required substring 
   public static int longestSubStr(String str){
      int len = str.length(); // getting the length of the string 
      int ans = 0; // variable to store the answer         
      int arr[] = new int[26]; // array to store the last index of the current character 
      Arrays.fill(arr, -1); // function to fill -1 at each index  
      int i = 0; // last pointer or slow pointer 
      // fast pointer, traversing over the string
      for(int j = 0; j < len; j++){ 
         // updating the value of the slow pointer 
         i = Math.max(i, arr[str.charAt(j)-'a'] + 1);            
         // updating the answer
         ans = Math.max(ans, j - i + 1); 
         // updating the index of the current character
         arr[str.charAt(j) - 'a'] = j;
      }        
      return ans; // return the final answer 
   }    
   // main function 
   public static void main(String []args){
   String str = "thisisthegivenstring"; // given string     
   // calling to the function 
   int ans = longestSubStr(str);    
   // print the final answer 
   System.out.println("The length of the longest substring that contains only unique characters is: " + ans );
   }
}

輸出

The length of the longest substring that contains only unique characters is: 8

時間和空間複雜度

以上程式碼的時間複雜度為O(N)，其中N是給定字串的長度。

以上程式碼的空間複雜度為常數或O(1)，因為我們在這裡沒有使用任何額外的空間。

結論

在本教程中，我們實現了一個Java程式來查詢最長無重複字元子字串的長度。我們實現了三種方法：第一種是查詢每個子字串，時間複雜度為O(N^3)，第二種是使用滑動視窗，時間複雜度為O(N^2)，第三種是雙指標方法。