Count Subsequences With Given Form

Moderate
0/80
profile
Contributed by
3 upvotes
Asked in companies
AmazonNagarro Software

Problem statement

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).
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1 :
2
abc
ababc
Sample output 1 :
1
5
Explanation For Sample Output 1 :
For the first test case:
The subsequence which can be of form “a^p * b^q * c^r” are: “abc” (p = 1, q = 1, r = 1).
So the count is 1.


For the second test case:
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).
Sample Input 2 :
2
abbabc
acba
Sample output 2 :
9
0
Hint

Check for every possible subsequence present in the string.

Approaches (2)
Brute Force

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:

  1. Include it in the current sequence.
  2. Exclude it in the current sequence.

 

Here is the algorithm:
 

  1. 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 “”).

 

  1. 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.
  2. Call the HELPER function recursively by excluding the current character.
  3. Similarly, call the HELPER function again by including the current character (‘CURR’ + ‘S[IDX]’).
  4. Return the sum of both the values returned by the above recursive calls.

 

isValid(‘CURR’)  (where ‘CURR’ is the string to be checked).
 

  1. Create a variable (say, iterator ‘i’).
  2. Run a loop till the characters of ‘CURR[i]’ are equal to ‘a’.
  3. Check if ‘i’ is equal to 0 or equal to the size of ‘CURR’.
    • Return FALSE.
  4. Create a variable (say, ‘TEMP’) and initialize it with ‘i’.
  5. Run a loop until ‘CURR[i]’ characters are equal to ‘b’.
  6. Check if ‘i’ is equal to ‘TEMP’ or equal to the size of ‘CURR’ or ‘CURR[i]’ is equal to ‘a’.
    • Return FALSE.
  7. Run a loop until ‘CURR[i]’ characters are equal to ‘c’.
  8. Check if ‘i’ is not equal to the size of ‘CURR’.
    • Return FALSE.
  9. Return TRUE.
Time Complexity

O((2 ^N ) * N), where ‘N’ is the size of the string.

 

Every character of the string has two choices, whether to include it in a subsequence or not. There are total ‘N’ characters, so the number of possible combinations will be 2 * 2 * 2… (‘N’ times). And for every subsequence, we check whether it is of the given form or not, which takes O(N) time. Therefore, the overall time complexity will be O((2 ^ N) * N).

Space Complexity

O(N), where ‘N’ is the size of the string.
 

The recursive stack for the HELPER function can contain at most the length of the string. Therefore, the overall space complexity will be O(N).

Code Solution
(100% EXP penalty)
Count Subsequences With Given Form
Full screen
Console