Last Updated: 25 Nov, 2021
Count Subsequences With Given Form
Moderate
Asked in companies
You are given a string ‘S’. Your task is to find the number of subsequences in string ‘S’ which are in the form of “a^p + b^q + c^r”, i.e., it consists of ‘p’ “a” characters, followed by ‘q’ “b” characters, and ‘r’ “c” characters, where ‘p’, ‘q’, and ‘r’ are greater than equal to 1. As the result can be large, return that number modulo 10^9 + 7.
Note :
1. A string ‘A’ is a subsequence of a string ‘B’ if ‘A’ can be obtained from ‘B’ by deleting several (possibly, zero or all) characters.
2. Two subsequences are considered different if the set of array indexes picked for the 2 subsequences are different.
Example :
Let the string be: ababc
The subsequence which can be of form “a^p * b^q * c^r” are: “abc” (p = 1, q = 1, r = 1), “abbc” (p = 1, q = 2, r = 1), “aabc” (p = 2, q = 1, r = 1)
So the count is 5 (“abc” can occur thrice).
Input Format :
The first line of the input contains an integer, 'T’, denoting the number of test cases.
The first line of each test case contains a string ‘S’.
Output Format :
For each test case, print the number of non-empty distinct palindromic subsequences modulo 10^9 + 7.
Print the output of each test case in a separate line.
Note :
You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints :
1 <= T <= 10
1 <= |S| <= 10^5
S consists of ‘a’, ‘b’, and ‘c’ characters only.
Where |S| denotes the length of ‘S’.
Time limit: 1 sec
Approaches
The basic idea is to find all the subsequences of the string and check whether it is of a given form or not. For each character of the string we have two choices with us:
- Include it in the current sequence.
- Exclude it in the current sequence.
Here is the algorithm:
- Call the function HELPER to find the subsequences and return the value returned by the function.
HELPER(‘S’, ‘IDX’, ‘CURR’) (where ‘S’ is the given string, ‘IDX’ is the current index, ‘CURR’ is the current subsequence which is initialized to “”).
- Base case:
- Check if ‘IDX’ is the size of the ‘S’.
- Check if ‘CURR’ is of the given form by calling the isValid function.
- Return 1.
- Return 0.
- Check if ‘CURR’ is of the given form by calling the isValid function.
- Check if ‘IDX’ is the size of the ‘S’.
- Call the HELPER function recursively by excluding the current character.
- Similarly, call the HELPER function again by including the current character (‘CURR’ + ‘S[IDX]’).
- Return the sum of both the values returned by the above recursive calls.
isValid(‘CURR’) (where ‘CURR’ is the string to be checked).
- Create a variable (say, iterator ‘i’).
- Run a loop till the characters of ‘CURR[i]’ are equal to ‘a’.
- Check if ‘i’ is equal to 0 or equal to the size of ‘CURR’.
- Return FALSE.
- Create a variable (say, ‘TEMP’) and initialize it with ‘i’.
- Run a loop until ‘CURR[i]’ characters are equal to ‘b’.
- Check if ‘i’ is equal to ‘TEMP’ or equal to the size of ‘CURR’ or ‘CURR[i]’ is equal to ‘a’.
- Return FALSE.
- Run a loop until ‘CURR[i]’ characters are equal to ‘c’.
- Check if ‘i’ is not equal to the size of ‘CURR’.
- Return FALSE.
- Return TRUE.
The basic idea is to store the occurrences for each character and find the count of subsequences simultaneously. We create three variables (say, ‘aCnt’, ‘bCnt’, and ‘cCnt’) whose functionalities are:
- ‘aCnt’: Let us consider a string “aa”. There will be three possibilities for this string (“a”, “a”, “aa”). If we get a new character ‘a’, the new subsequences will be previous subsequences, previous subsequences + the new ‘a’, and the new ‘a’ alone. So the total will be ‘aCnt’ + ‘aCnt’ + 1, i.e., 2 * ‘aCnt’ + 1.
- ‘bCnt’: Let us consider a string “aab”. There will be three possibilities for this string (“ab”, “ab”, “aab”). If we get a new character ‘b’, the new subsequences will be previous subsequences, previous subsequences + the new ‘b’, and the new ‘b’ alone (which is equal to ‘aCnt’). So the total will be ‘bCnt’ + ‘bCnt’ + ‘aCnt’, i.e., 2 * ‘bCnt’ + ‘aCnt.
- Similarly, we can find ‘cCnt’.
The total number of subsequences will be stored in the ‘cCnt’ as it contains the last character ‘c’.
Here is the algorithm :
- Create three variables (say, ‘aCnt’, ‘bCnt’, and ‘cCnt’) to store the counts of subsequences made by the combination of ‘a’, ‘b’, and ‘c’, respectively, and initialize them with 0.
- Run a loop from 0 to the size of the string (say, iterator ‘i’) to traverse the string.
- Check if ‘S[i]’ is equal to ‘a’.
- Update ‘aCnt’ with the sum of 1 and ‘2’ * ‘aCnt’.
- Check if ‘S[i]’ is equal to ‘b’.
- Update ‘bCnt’ with the sum of ‘aCnt’ and ‘2’ * ‘bCnt’.
- Else,
- Update ‘cCnt’ with the sum of ‘bCnt’ and ‘2’ * ‘cCnt’.
- Return ‘cCnt’.