Checks whether the given string can only be split into subsequences of ABC

A subsequence of a string is a portion of a string where characters can be taken from any position (zero or more elements) of the string without changing the order of the characters and Form a new string. In this problem, we are given a string of length N where every character of the string is either an 'A', 'B' or 'C' character. Our task is to find that the string can only be split into subsequences "ABC" or "Not". Returns "yes" if the string is only split into the subsequence "ABC", otherwise returns "no".

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

Instructions - The method of splitting is to split the string into 2 subsequences of "ABC", as follows -

• One possible method is to form the subsequence "ABC" by taking the characters with indexes 0, 2, and 3, and then form the subsequence "ABC" by taking the characters with indexes 1, 4, and 5 .

• Another possible way is to form the subsequence "ABC" by getting the characters at indexes 0, 4, 5 and 1, 2, 3.

Therefore, the string can be split into 2 subsequences of "ABC".

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

Explanation - For 'A' occurring at index number 5, there is no 'B' after it. Therefore, the entire string cannot be split into unique subsequences "ABC". Therefore, the answer is "no".

Method 1: Use Hashmap

We have two observations as follows -

• The size of the string should be divisible by 3 because we need to split the string into "ABC" and the number of characters 'A', 'B' and 'C' should be equal. Otherwise, we cannot meet the conditions.

• When we count the frequency of characters "A", "B" and "C", the count of "A" must be greater than or equal to the count of "B" and the count of "B" must be greater than or equal to 'C ' count. Because A's count >= B's count >= C's cout

Based on the above observations, we have three conditions to check.

• Expected string size % 3 == 0.

• should be the count of A >= the count of B >= the count of C.

• The last condition should be freq[ ‘A’ ] == freq[ ‘B’ ] == freq[ ‘C’ ] .

We can use a hash map to solve this problem since we need to store the frequency of each character in the given string "str".

Let us discuss the following method step by step -

• First we will create a function called "checkSubsequences" which will take the given string "str" ​​as parameter and return the desired string "yes" if possible , otherwise "no" is returned as the return value.

• In the function, all the steps are given below-

• Create variable "len" to store the length of the string.

• Check the first condition and return 'no' if the length is not divisible by 3.

• Create a hash map to store the frequencies of characters 'A', 'B' and 'C'. Therefore, the space complexity is constant.

• Use a for loop to traverse the string from 0 to less than len.

  • Increase the current character count of the string

  • Check the second condition and return "No" if "A"'s count is less than "B"'s count or "B"'s count is less than "C"'s count.

• After the for loop, we have to check the last third condition and return "No" if A's count is not equal to B's count or B's count is not equal to C's count.

• Finally, when all conditions are met, return "yes".

Example

#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;
}

Output

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

Time and space complexity

The time complexity of the above code is O(N) because we traverse the string. where N is the size of the string.

The space complexity of the above code is O(1) because we are storing the frequency of numbers, whose size is constant 3.

in conclusion

In this tutorial, we implemented a program to check if a given string can only be split into subsequences ABC. We implemented a hashing method because we had to store the frequencies. In this method, we mainly check three conditions, if all conditions are met, it means that we can only split the string into subsequences of "ABC".

The above is the detailed content of Checks whether the given string can only be split into subsequences of ABC. For more information, please follow other related articles on the PHP Chinese website!