Number of special subsequences in a string

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

1. If current character is ‘a’, then there are following possibilities :
   1. ‘a’ begins a new subsequence.
   2. It is part of aCount subsequences, where aCount is number of a encountered till index i.
   3. It is not part of aCount subsequences.

   Therefore  aCount = (1 + 2 * aCount)

2. Similary if current character is ‘b’, then there are following possibilities :
   1. 1. It begins a new subsequence of b’s with aCount subsequences.
      2. It is part of bCount subsequences.
      3. It is not part of bCount subsequences.

   Therefore bCount = (aCount + 2 * bCount)

3. Similary if current character is ‘c’, then cCount is given by
   cCount = (bCount + 2 * cCount);

Finally cCount gives the number special subsequence.