Power Subsequences

Moderate
0/80
Average time to solve is 25m
profile
Contributed by
0 upvote
Asked in companies
HSBCLTI - Larsen & Toubro Infotech

Problem statement

You are given a string S, which is formed by characters ‘A’, ‘B’ and ‘C’. You need to count the number of Power Subsequences of the given string S.

Note:

1. A subsequence of string S is a string which we get after removal of zero or more characters from S, and without changing the order of character in the remaining string.

2. A subsequence S’ of string S, is known as Power Subsequence if S’ can be represented in the form ‘A’^i + ‘B’^j + ‘C’^k where i, j and k are strictly greater than 0, ie. S’ can be written as a concatenation of I ‘A’s, followed by j ‘B’s, followed by k ‘C’s. 

3. Eg. “ABC” is a Power Subsequence with i=j=k=1, while “BAC” or “AB” or “BC” are not Power Subsequences.

4. Two subsequences are considered different if and only if the set of indexes of string S, chosen for two subsequences, are different.
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 and only line of each test case consists of a string S.
Output format: 
For each test case, print an integer that denotes the count of the number of Power Subsequences of the given string S in a separate line.

As the number of Power Subsequences can be large that's why print it modulo 10^9 +7.
Note: 
You don't have to print anything, it has already been taken care of. Just Implement the given function.
Constraints: 
1 <= T <= 100
1 <= |S| <= 10^4

Were |S| denotes the length of given string S.

Time Limit: 1 sec
Sample Input 1:
1
ABBC
Sample Output 1:
3
Explanation For Sample Input 1:
There are 3 power subsequences for a given input string: ABC, ABC and ABBC.
Sample Input 2:
1
AABBC
Sample Output2:
9
Explanation For Sample Input 2:
There are 9 power subsequences for a given input string: ABC, ABC, ABC, ABC, ABBC, ABBC, AABC, AABC, AABBC.
Hint

Generate all possible subsequences of string S and count the power subsequences.

Approaches (2)
Brute Force
  1. Generate all possible subsequences of the given string S.
  2. Make a recursive function that takes in given string S, the current index I, and the current subsequence.
  3. The base condition for this recursive function is when ‘i’ becomes equal to the length of the given string S.
  4. When we reach the base condition, check the current subsequence whether it is Power Subsequence or not. If it returns 1 else return 0.
  5. For checking whether a given subsequence is Power subsequence or not do the following:
    • Make 4 variables that will store the position of:
      • Last occurrence of ‘A’.
      • First occurrence of ‘B’.
      • Last occurrence of ‘B’.
      • First occurrence of ‘C’.
    • Initialize these variables with -1 and iterate through the subsequence and update the values of these variables.
    • The subsequence will the power subsequence if the following conditions met:
      • The position of the Last occurrence of ‘A’ is not -1 and it is strictly less than the position of the first occurrence of ‘B’.
      • The position of the Last occurrence of ‘B’ is strictly less than the first position of occurrence of ‘C’.
    • Eg. In string “ABBC”
      • The last occurrence of ‘A’ is 0, the First occurrence of ‘B’ is 1, the last occurrence of ‘B’ is 2 and the first occurrence of ‘C’ is 3 (Considering 0 based indexing).
      • All the above conditions are met, hence it is a power sequence.
  6. If the base condition does not meet, from Inside this recursive function makes 2 recursive calls:
    • First recursive call without considering the ith character and pass i+1.
    • Second recursive call with appending the ith character at the end of current subsequence and pass i+1.
  7. Finally, return summation of return values of both of these recursive calls.

Eg. for string “ABC '', let's assume solve is the name of our recursive function.

solve(“ABC”, 0, “”)

    solve(“ABC”, 1, “”)

        solve(“ABC”, 2, “”)

            solve(“ABC”, 3, “”)

                Return 0

            solve(“ABC”, 3, “C”)

                Return 0

            Return 0

        solve(“ABC”, 2, “B”)

            solve(“ABC”, 3, “B”)

                Return 0

            solve(“ABC”, 3, “BC”)

                Return 0

            Return 0

        Return 0

    solve(“ABC”, 1, “A”)

        solve(“ABC”, 2, “A”)

            solve(“ABC”, 3, “A”)

                Return 0

            solve(“ABC”, 3, “AC”)

                Return 0

            Return 0

        solve(“ABC”, 2, “AB”)

            solve(“ABC”, 3, “AB”)

                Return 0

            solve(“ABC”, 3, “ABC”)

                Return 1 // Because ABC is a power subsequence.

            Return 1

        Return 1

    Return 1

This way we get 1 as the count of power subsequences.

Time Complexity

O((2^N) * N), where N is the length of the given string S.

 

As there are 2^N possible subsequences for a string of length N and checking if the subsequence is a power sequence or not, takes an additional O(N) order of time for each subsequence.

Space Complexity

O(N), where N is the length of a given string S.

 

 As we are using recursion for generating subsequence and this will use O(N) stack memory.

Code Solution
(100% EXP penalty)
Power Subsequences
Full screen
Console