C++ 包含C2、以C1开头和以C3结尾的最长子字符串

子字符串是通过从给定字符串的开头和结尾删除一些字符（可能为0个或全部）而得到的字符串。我们给定一个字符串和三个字符，并且必须找出包含所有三个给定字符的、以c1、c2和c3的顺序开头和以c3结尾的最长子字符串。此外，给定的字符可能相同，但我们的字符串必须包含不同的字符。

输入

string str = "abacdeab"
char c1 = a 
char c2 = b
char c3 = c

输出

"abac"

说明

从字符’a’开始的子字符串只有三种可能的索引，它们分别是0、2和6。现在，子字符串只能在索引3处的字符’c’结束。

对于第三个条件，子字符串中必须包含字符’b’，因此所需的字符串是从0到3的子字符串。

方法

我们已经看过以上的示例，现在让我们来看看实现程序所需的步骤。

• 首先，我们需要定义一个函数，该函数将接受一个字符串和三个给定的字符作为参数，并返回一个整数值作为返回值。

• 在函数中，我们将获取字符串的长度，并创建一个整数变量来查找第一个字符的第一个实例。

• 我们将使用该变量遍历字符串，并在找到第一个字符的第一个实例时中断循环，如果没有找到则返回一个空字符串。

• 现在，我们将创建一个变量来标记我们是否已经找到了字符2，并创建另一个变量来存储字符3的最后位置。

• 我们将从找到第一个字符的第一个实例的下一个索引开始遍历字符串，并查找第二个和第三个字符。

• 如果第二个字符出现在任何位置，则标记为已找到，如果我们处理第三个字符时已经找到了第二个字符，则标记第三个字符的位置。

• 最后，我们将返回给定字符串指针的第一个和第三个字符之间的子字符串。

示例

#include <bits/stdc++.h>
using namespace std;

// function to find the required substring 
string getString(string str, char char1, char char2, char char3){
   int len = str.length(); // getting length of the string     
   // traversing over the array to get the first occurrence of char1
   int i = 0;
   for(; i<len; i++){
      // if current character is char1 break
      if(str[i] == char1){
         break;
      }
   }   
   // if not char1 present return empty string 
   if(i == len){
      return "";
   }
   int start = i; // variable to store the starting index 
   bool isFound = false; // variable to mark whether char2 is found or not 
   int lastIdx = i-1; // variable to store last index of char3 

   // again traversing over the array from next index of i
   i++;
   for(; i<len; i++){
      if(str[i] == char2){
         isFound = true;
      } else if((str[i] == char3) and (isFound)){
         lastIdx = i;
      }
   }
   // return the final string 
   return str.substr(start, lastIdx-start + 1);
}
int main(){
   string str = "thisisthestring";
   char char1 = 'i';
   char char2 = 'e';
   char char3 = 'r';
   // calling the function to get the answer 
   string ans = getString(str, char1, char2, char3);
   if(ans == ""){
      // if the returned value is empty
      cout<<"The given string does not contain any substring with given characters present in the sequence"<<endl;
   } else {
      cout<<"The length of the required string is: "<<ans.length()<<" and the string is: "<<ans<<endl;
   }
   return 0;
}

输出

The length of the required string is: 10 and the string is: isisthestr

时间和空间复杂度

上述代码的时间复杂度是O(N)，因为我们只需要遍历一次数组。

由于我们没有使用任何额外的空间，所以上述代码的空间复杂度是常数或O(1)。

结论

在本教程中，我们实现了一个程序，用于找到给定字符串中以给定字符开头、以不同字符结尾的最长子字符串的长度。此外，它必须在其中包含第三个给定字符。我们使用for循环在线性时间复杂度和常量的额外空间下实现了该程序。