Dear reader, let's try to solve some more problems on DP, to make our understanding of the topic more clear. Today we will solve a really nice problem.
Important Links : Problem Link, Solution Video
Let's understand the question first.
Prev Next
Count A+B+C+ Subsequences
Learning to code is useful no matter what your career ambitions are.
~ Arianna Huffington
Count A+B+C+ Subsequences
Problem Discussion :
- You are given a string str.
- You are required to calculate and print the count of subsequences of the nature a+b+c+.
For abbc -> there are 3 subsequences. abc, abc, abbc
For abcabc -> there are 7 subsequences. abc, abc, abbc, aabc, abcc, abc, abc.
Approach :
Now, first let's say we have a couple of substring like {"ab", "a", "aa", "abc", "aabcc"}
We will append "a" "b" and "c" one at a time and check if the resultant subsequence follows the a+b+c+ pattern.
Appending "a"
We cannot append a to "ab" because that will make it "aba" which doesn't follow the pattern. Similarly, we cannot append to "abc", "aabcc". So one pattern that arises is we had to append "a" to some strings such that after appending it follows the a+b+c+ pattern, then for sure the string has to be a+ like "a", "aaa", "aaaaaaa". Only then we can do that.
Appending "b"
We cannot "b" to "abc". Because it will make it "abcb" which doesn't satisfy the a+b+c+ pattern. We can only append "b" to "ab", "a", "aa". Clearly, for "b" the valid strings are a+, and a+b+.
Appending "c"
At this point, you might have already guessed the approach. We can only add it to "ab", "abc", and "aabcc". We can only append "c" to a+b+ and a+b+c form.
Now, let's look at another thing.
Let's say at this point we have x strings which are of the form a+. Also, we may or may not append a new "a" to those x strings. What will be the total number of valid a+ strings? The answer is 2x+1. You can take a look at the illustration below why 2x+1. We can either append the new "a" at the end. The new "a" is shown in orange color. Or we may not. This alone gives us 2x. The extra one is when we just consider the new "a".
What if we had x a+ form of string and y a+b+ form of strings and we may or may not want to append "b". Then what will be the total number of valid a+b+ strings?
In this case, it will be 2y+x. How? Take a look at the illustration below.
Here we had 2 a+ forms of strings and 3 a+b+ forms of strings. They formed 2y+x number of a+b+ strings.
Now for c it will be the same. i.e If we have x a+b+ form of strings and y a+b+c+ form of strings then the total number of final strings will be 2x+y.
With this understanding, we can actually move forward with our dp table. We will create a 3xN length dp table. Since we have 3 states a+, a+b+, and a+b+c+. Also when we will deal with "a" we will just consider the count of a+. If we deal with "b" we will consider the count of a+b+ and a+. If we deal with "c' we will consider the count of a+b+c+ and a+b+.
The string in consideration is "abcabc". The second "abc" is denoted as "a`b`c`" to differentiate and help us understand.
Trivial case is all zero. And we start with the first character "a'. And clearly a+ will be 1.
Next when we consider "b", as we said it will be 2x+y. Here x is 0 but y is 1 so b will have one string. And it does actually have 1 string. "b" will not affect the other two states except "a+b+", so those values will be the same as previous.
Now we come to "c". As we discussed before c will be 2x+y. Here x=0 but y=1. So the value will be 1 and in reality, too it will have only one string.
Now, I insist you continue this way and complete the grid. I am attaching the final state below.
If you faced any difficulty understanding this watch the solution video.
Let's move onto code.
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws Exception {
Scanner scn = new Scanner(System.in);
String str = scn.next();
int a = 0;
int ab = 0;
int abc = 0;
for (int i = 0; i < str.length(); i++) {
char ch = str.charAt(i);
if (ch == 'a') {
a = 2 * a + 1;
} else if (ch == 'b') {
ab = 2 * ab + a;
} else if (ch == 'c') {
abc = 2 * abc + ab;
}
}
System.out.println(abc);
scn.close();
}
}
java;
true";
Analysis
Time Complexity :
Again we are using a single loop and performing O(1) operations inside it. Hence, it will give us a total of O(n) operations.
SPACE COMPLEXITY :
We are not using any extra array for solving, so the space complexity is O(1). We could have maintained a dp array. But since we will just be allocating the last element, we can get rid of it.
