Last Updated: 22 Dec, 2020
Power Subsequences
Moderate
Asked in companies
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.
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
Approaches
- Generate all possible subsequences of the given string S.
- Make a recursive function that takes in given string S, the current index I, and the current subsequence.
- The base condition for this recursive function is when ‘i’ becomes equal to the length of the given string S.
- When we reach the base condition, check the current subsequence whether it is Power Subsequence or not. If it returns 1 else return 0.
- 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.
- Make 4 variables that will store the position of:
- 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.
- 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.
- Here key idea it to store count of subsequences of type ‘A’^i, ‘A’^i + ‘B’^j and ‘A’^i + ‘B’^j + ‘C’^k, let's say countA, countB and countC respectively, at each index (lets say idx) of the string.
- Initially countA, countB and countC is initialised with zero.
- Iterate through the string from left to right.
- If idx’th character is ‘A’, then countA will be updated as follows:
- countA are the count of subsequences of type ‘A’^i and we can append ‘A’ in all of these subsequences and get countA more subsequences. Also, the current single ‘A’ character is also a valid subsequence of type ‘A’^i.
- Therefore, countA will be updated as:
- countA = countA + countA + 1.
- If idx’th character is ‘B’, then countB will be updated as follows:
- countB is the count of subsequences of type ‘A’^i + ‘B’^j and we can append ‘B’ in all of these subsequences and get countB more subsequences. Also appending ‘B’ in sequences of type ‘A’^i will also result in a valid subsequence of type ‘A’^i + ‘B’^j.
- Therefore, countB will be updated as:
- countB = countB + countB + countA.
- If idx’th character is ‘C’, then countC will be updated as follows:
- countC is the count of subsequences of type ‘A’^i + ‘B’^j + ‘C’^k and we can append ‘C’ in all of these subsequences and get countC more subsequences. Also appending ‘C’ in subsequences of type ‘A’^i + ‘B’^j will also result in a valid subsequence of type ‘A’^i + ‘B’^j + ‘C’^k.
- Therefore, countC will be updated as:
- countC = countC + countC + countB.
- After the traversal through the string the required count of power subsequences will be stored in variable countC.
- The answer may be very large, hence after each updation of countA, countB or countC, we check whether the value exceeds 10^9+7 or not. If it is, we just simply take mod with 10^9+7.