You are given a String S of length N. Now, a special subsequence is one that can be represented in the form a^i b^j c^k, where i≥1, j≥1 and k≥1. In short, a special subsequence is a subsequence that first consist of i ′a′ characters, followed by j ′b′ characters, followed by k ′c′ characters, where i≥1, j≥1 and k≥1
Now, you need to find the number of special subsequences of String S. Two subsequences are considered different if the set of array indexes picked for the 2 subsequences are different. For example :
Sample Input : abcabc
Output : 7
Subsequences are abc, abc, abbc, aabc
abcc, abc and abc
For the purpose of the answer let’s define:
- abc-good : String is a string in the form aibjck, for i,j,k≥1
- ab-good : String is a string in the form aibj, for i,j≥1
- a-good : String is a string in the form ai, for i≥1
We are interested in the number of abc-good subsequences of the input string S[1…N].
Let fabc[x] be the number of abc-good subsequences of S[1…x]. Any abc-good subsequence of S[1…x] is either any abc-good subsequence of S[1…x−1], or if S[x]=c it is any abc-good subsequence of S[1…x−1] extended with S[x], or if S[x]=c it is any ab-good subsequence of S[x−1]. Similar reasoning holds for fab[x] and fa[x].
So to find the count of special subsequence, traverse given string. For every character S[i] do following
- If current character is ‘a’, then there are following possibilities :
- ‘a’ begins a new subsequence.
- It is part of aCount subsequences, where aCount is number of a encountered till index i.
- It is not part of aCount subsequences.
Therefore aCount = (1 + 2 * aCount)
- Similary if current character is ‘b’, then there are following possibilities :
- It begins a new subsequence of b’s with aCount subsequences.
- It is part of bCount subsequences.
- It is not part of bCount subsequences.
Therefore bCount = (aCount + 2 * bCount)
- Similary if current character is ‘c’, then cCount is given by
cCount = (bCount + 2 * cCount);
Finally cCount gives the number special subsequence.