找到最小的 K，使得每個長度至少為 K 的子字串都包含字元 c

---

在本問題中給定一個字串，我們需要找到一個最小的長度 'k'，使得給定字串的所有長度為 k 的子字串都包含至少一個共同的字元。我們將看到解決此問題的三種方法，一種是找到所有子字串的樸素方法，另一種是二分查詢方法，第三種是使用最小差值方法。

示例

string str = “efabc”
Output: 3

解釋

對於長度為 1 和 2 的子字串，不可能包含相同的字元，例如子字串 'ef' 和 'bc' 沒有任何相同的字元。但是對於長度為 3 或更長的子字串，'a' 將始終存在。

樸素方法

在這種方法中，我們將生成所有子字串，並對所有子字串檢查是否有任何字元是共同的，但這種方法將花費非常多的時間。

示例

#include <bits/stdc++.h>
using namespace std; 
// function to find the minimum length of the substring 
int minLen(string str){
   int n = str.length(); // length of the given string
   
   // finding all the substrings fo the same length 
   for(int len = 1; len <= n; len++){
      int freq[26] = {0}; // frequency array to store the frequency         
      for(int i=0; i<=n-len; i++){
         int j = i+len; // ending of the current substring 
         int cur[26] = {0};
         for(int k = i; k<j; k++){
    	      if(cur[str[k]-'a']){
    		      continue;
            }
            
            // storing the frequecy of the letters 
            freq[str[k]-'a']++;  
    	      cur[str[k]-'a']++; 
         }
      }        
      
      // total number of substring with this length 
      int scount = n-len+1;
      
      // if any character have the same frequecy then we will return current length 
      for(int i=0; i<26; i++){
         if(freq[i] == scount){
            return len;
         }
      }
   }
   return n;
}

// main function 
int main(){
   string str = "efabc"; // given string    
   
   // calling the function 
   cout<<"The minimum length of the substrings that contains at least a same character is "<<minLen(str)<<endl;
   return 0;
}

輸出

The minimum length of the substrings that contains at least a same character is 3

時間和空間複雜度

以上程式碼的時間複雜度為 O(N^3)，其中 N 是給定字串的大小。以上程式碼的空間複雜度為 O(1)，因為我們使用了常數空間。

二分查詢

在這種方法中，我們將使用二分查詢技術來找到最小的子字串長度。我們將遍歷每個字元的子字串，並檢查需要多少最小的子字串長度，並在答案上使用二分查詢。

示例

#include <bits/stdc++.h>
using namespace std; 
// function to check last occurence 
bool check(int len, string str){
   int n = str.length();    
   for(int i=0; i< 26; i++){
      int last = -1;
      int cur = 'a'+i;
      int j;
      for(j=0; j < n; j++){
         if(str[j] == cur){
            if(j-len > last){
               break;
            }
            else{
               last = j;
            }
         }
      }
      if(j != n || j-len > last){
         continue;
      }
      else{
         return true;
      }
   }
   return false;
}

// function to find the minimum length of the substring 
int minLen(string str){
   int n = str.length(); // length of the given string    
   int l = 1, h = n;
   int ans;
   while (l <= h){
      int len = (l + h) / 2;
      if (check(len, str)) {
         ans = len;
         h = len - 1;
      }
      else
         l = len + 1;
   }
   return ans;
}

// main function 
int main(){
   string str = "aaabaaa"; // given string    
   // calling the function 
   cout<<"The minimum length of the substrings that contains at least a same character is "<<minLen(str)<<endl;
   return 0;
}

輸出

The minimum length of the substrings that contains at least a same character is 2

時間和空間複雜度

以上程式碼的時間複雜度為 O(N*log(N))，其中 N 是給定字串的大小。以上程式碼的空間複雜度為 O(1)，因為我們使用了常數空間。

高效方法

在這種方法中，我們遍歷了字串，並且對於每個小寫英文字母字元，我們都維護了最後一次出現以及每個兩個相同字元之間的間隔、給定字串的起始和結束位置。

示例

#include <bits/stdc++.h>
using namespace std; 
// function to find the minimum length of the substring 
int minLen(string str){
   int last[26]; // array to store the last occurrence, of the characters
   memset(last,-1,sizeof(last)); // making start of each character equal to -1    
   int minLen[26]; // array to store minimum length of substring for each char
   
   // initializing to length of string
   int n = str.length();    
   for(int i=0; i<26; i++){
      minLen[i] =  -1;
   }   
   
   // traversing over the string to get the answer 
   int ans = n;
   for(int i=0; i<n; i++){
      if(minLen[str[i]-'a'] == -1){
         minLen[str[i]-'a'] = i+1;
      }
      else{
         minLen[str[i]-'a'] = max(minLen[str[i]-'a'], i-last[str[i]-'a']);  
      }
      last[str[i]-'a'] = i;
   }
   for(int i=0; i<26; i++){
      minLen[i] = max(minLen[i], n-last[i]);
      ans = min(ans, minLen[i]);
   }
   return ans;
}

// main function 
int main(){
   string str = "efabc"; // given string     
   // calling the function 
   cout<<"The minimum length of the substrings that contains at least a same character is "<<minLen(str)<<endl;
   return 0;
}

輸出

The minimum length of the substrings that contains at least a same character is 3

時間和空間複雜度

以上程式碼的時間複雜度為 O(N)，這是線性時間複雜度。以上程式碼的空間複雜度為 O(1)，因為我們使用了常數空間。

結論

在本教程中，我們實現了查詢包含至少一個相同字元的子字串的最小長度的程式碼。我們已經實現了三種方法來找到解決方案。第一種方法是樸素方法，具有非常高的時間複雜度。第二種方法是二分查詢方法，最後一種方法是高效的線性時間複雜度方法。