找到最小的 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)，因为我们使用了常数空间。

结论

在本教程中，我们实现了查找包含至少一个相同字符的子字符串的最小长度的代码。我们已经实现了三种方法来找到解决方案。第一种方法是朴素方法，具有非常高的时间复杂度。第二种方法是二分查找方法，最后一种方法是高效的线性时间复杂度方法。