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)，第三种是双指针方法。