spider68

Count subsequences of type a^i b^j c^k

Jun 29th, 2020
210
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.44 KB | None | 0 0
  1. //Given a string s, the task is to count number of subsequences of the form aibjck, where i >= 1, j >=1 and k >= 1.
  2.  
  3. #include <iostream>
  4. using namespace std;
  5.  
  6. int main() {
  7.     int i,j,t,n;
  8.     cin>>t;
  9.     while(t--)
  10.     {
  11.         string s;
  12.         cin>>s;
  13.         int a=0,b=0,c=0;
  14.         for(i=0;i<s.length();i++)
  15.         {
  16.             if(s[i]=='a')a=1+2*a;
  17.             else if(s[i]=='b')b=a+2*b;
  18.             else c=b+2*c;
  19.         }
  20.         cout<<c<<endl;
  21.     }
  22.     return 0;
  23. }
Add Comment
Please, Sign In to add comment