检查给定的字符串是否只能被拆分为ABC的子序列

字符串的子序列是指字符串的一部分，其中可以从字符串的任何位置（零个或多个元素）取出字符，而无需更改字符的顺序并形成新的字符串。在这个问题中，我们给出了一个长度为 N 的字符串，其中字符串的每个字符都属于“A”、“B”或“C”字符。我们的任务是找到该字符串只能拆分为子序列“ABC”或“Not”。如果字符串仅拆分为子序列“ABC”，则返回“yes”，否则返回“no”。

Input 1: str = “AABCBC” 
Output 1: yes

说明 - 分割的方式是将字符串分割成“ABC”的2个子序列，如下 -

• 其中一种可能的方法是，通过取索引为0、2、3的字符形成子序列“ABC”，然后通过取索引为1、4、5的字符形成子序列“ABC”。

• 另一种可能的方法是，通过在索引0、4、5和1、2、3处获取字符来形成子序列“ABC”。

因此，字符串可以拆分为“ABC”的 2 个子序列。

Input 2: str = “AABBBACCC”
Output 2: no

解释 - 对于在索引号5处出现的'A'，之后没有'B'。因此，整个字符串不能被分割为唯一的子序列"ABC"。因此，答案是"no"。

方法1：使用Hashmap

我们有两个观察结果如下 -

• 字符串的大小应该能被3整除，因为我们需要将字符串分割为“ABC”，并且字符'A'、'B'和'C'的数量应该相等。否则，我们无法满足条件。

• 当我们计算字符“A”、“B”和“C”的频率时，“A”的计数必须大于等于“B”的计数和“B”的计数' 必须大于等于 'C' 的计数。因为 A 的计数 >= B 的计数 >= C 的 cout

根据上述观察，我们有三个条件要检查。

• 应为字符串大小 % 3 == 0。

• 应该是 A 的计数 >= B 的计数 >= C 的计数。

• 最后一个条件应该是 freq[ ‘A’ ] == freq[ ‘B’ ] == freq[ ‘C’ ] 。

我们可以使用哈希映射来解决这个问题，因为我们需要存储给定字符串“str”中每个字符的频率。

让我们逐步讨论下面的方法-

• 首先，我们将创建一个名为“checkSubsequences”的函数，该函数将以给定的字符串“str”作为参数，并在可能的情况下返回所需的字符串“yes”，否则返回“no”作为返回值。

• 在函数中，下面给出了所有步骤-

• 创建变量“len”来存储字符串的长度。

• 检查第一个条件，如果长度不能被3整除，则返回'no'。

• 创建一个哈希映射来存储字符'A'、'B'和'C'的频率。因此，空间复杂度是常数。

• 使用for循环从0到小于len遍历字符串。

  • 增加字符串当前字符的计数

  • 检查第二个条件，如果“A”的计数小于“B”的计数或“B”的计数小于“C”的计数，则返回“否”。

    li>

• 在 for 循环之后，我们必须检查最后的第三个条件，如果 A 的计数不等于 B 的计数或 B 的计数不等于 C 的计数，则返回“否”。

• 最后，当所有条件都满足时，返回“yes”。

示例

#include <bits/stdc++.h>
using namespace std;
// function to check subsequences of "ABC"
string checkSubsequences( string str ){
   int len = str.size(); //getting length of the string str
   // check first condition 
   if( len%3 != 0 ) {
      return "no";
   }
   map< char, int >freq; //store the count of character 'A', 'B' and 'C'
   for( int i=0; i<len; i++){
      freq[ str[i] ]++; // increase the count of the character
      //chech second condition 
      if(freq[ 'A' ] < freq[ 'B' ] || freq[ 'B' ] < freq[ 'C' ]){
         return "no";
      }
   }
   //check third condition 
   if(freq[ 'A' ] != freq[ 'B' ] || freq[ 'B' ] != freq[ 'C' ]){
      return "no";
   }
   // it is possible to split string only into subsequences of "ABC"
   return "yes";
}
// main function 
int main(){
   string str = "ABAAABCBC";// given string 
   // calling the function 'checkSubsequences' to check is it possible to split
   // string into subsequences of "ABC"
   string result = checkSubsequences( str );
   if( result == "yes" ){
      cout<< result << ", the string is splited only into the subsequences of ABC";
   }
   else {
      cout<< result << ", the string is not splited only into the subsequences of ABC.";
   }
   return 0;
}

输出

no, the string is not splited only into the subsequences of ABC.

时间和空间复杂度

上述代码的时间复杂度为O(N)，因为我们遍历了字符串。其中N是字符串的大小。

上述代码的空间复杂度为 O(1)，因为我们存储的是数字的频率，其大小恒定为 3。

结论

在本教程中，我们实现了一个程序来检查给定的字符串是否只能拆分为子序列 ABC。我们实施了一种散列方法，因为我们必须存储频率。在这种方法中，我们主要检查三个条件，如果所有条件都满足，则意味着我们只能将字符串拆分为“ABC”的子序列。

以上是检查给定的字符串是否只能被拆分为ABC的子序列的详细内容。更多信息请关注PHP中文网其他相关文章！