C++ 使每个长度至少为K的子字符串都包含一个字符c的最小K值

在这个问题中给出了一个字符串，我们需要找到一个最小长度的’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)，因为我们使用的是常数空间。

结论

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