Favorite Subsequence


You are given a String \nS of length N.\n\nNow, a good subsequence is one that can be represented in the form aibjck, where i1, \nj1 and \nk1. For example ,if \ni=2,\nj=1,\nk=3, it represents the string \naabccc. In short, a good subsequence is a subsequence that first consist of i acharacters, followed by j \nb’ characters, followed by \nk c characters, where i1, \nj1 and k1\n\nNow, you need to find the number of good subsequences of String S. As the number of such subsequences could be rather large, print the answer Modulo \n10^9+7.\n\nNote1: Two subsequences are considered different if the set of array indexes picked for the 2 subsequences are different.\n\nInput Format:\n\nThe first and only line of input contains the S\nOutput Format :\n\nPrint the required answer on a single line.\n\nConstraints:\n\n1|S|10^5.


#include <bits/stdc++.h>
using namespace std;
int countSubsequences(string s)
    int aCount = 0;
    int bCount = 0;
    int cCount = 0;
    for (unsigned int i=0; i<s.size(); i++)
        if (s[i] == 'a')
            aCount = (1 + 2 * aCount);
        else if (s[i] == 'b')
            bCount = (aCount + 2 * bCount);
        else if (s[i] == 'c')
            cCount = (bCount + 2 * cCount);
    return cCount;
int main()
    string s;
  	cin >> s;
    cout << countSubsequences(s) << endl;
    return 0;
Ads Blocker Image Powered by Code Help Pro

Ads Blocker Detected!!!

We have detected that you are using extensions to block ads. Please support us by disabling these ads blocker.

Powered By
CHP Adblock Detector Plugin | Codehelppro