字符串的子序列是指字符串的一部分，其中可以从字符串的任何位置（零个或多个元素）取出字符，而无需更改字符的顺序并形成新的字符串。在这个问题中，我们给出了一个长度为 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 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"; } mapfreq; //store the count of character 'A', 'B' and 'C' for( int i=0; i
输出
no, the string is not splited only into the subsequences of ABC.登录后复制
时间和空间复杂度
上述代码的时间复杂度为O(N)，因为我们遍历了字符串。其中N是字符串的大小。
上述代码的空间复杂度为 O(1)，因为我们存储的是数字的频率，其大小恒定为 3。
结论
在本教程中，我们实现了一个程序来检查给定的字符串是否只能拆分为子序列 ABC。我们实施了一种散列方法，因为我们必须存储频率。在这种方法中，我们主要检查三个条件，如果所有条件都满足，则意味着我们只能将字符串拆分为“ABC”的子序列。
以上就是检查给定的字符串是否只能被拆分为ABC的子序列的详细内容，更多请关注【创想鸟】其它相关文章！
