Problem Statement
Given two strings s1 and s2, the task is to count how many subsequences of s1 are exactly equal to s2.
A subsequence is formed by deleting zero or more characters from a string without changing the order of the remaining characters.
Example 1
Input
s1 = "geeksforgeeks"
s2 = "gks"
Output
4
There are four different ways to pick characters from s1 so that they form "gks".
Example 2
Input
s1 = "problemoftheday"
s2 = "geek"
Output
0
Since the characters required to form "geek" do not appear in the required order, the answer is 0.
Brute Force Approach
The first idea that comes to mind is to generate every possible subsequence of s1 and compare each one with s2.
Although this works conceptually, it is extremely inefficient because a string of length n has 2^n subsequences. With n up to 1000, this approach is impossible.
We need a smarter solution.
Dynamic Programming Insight
The key observation is that while scanning s1, every character gives us two choices:
Since many subproblems repeat, Dynamic Programming (DP) is the perfect approach.
We define:
dp[i][j]
as the number of ways to form the first j characters of s2 using the first i characters of s1.
For example:
dp[5][2]
means the number of ways to create the first two characters of s2 using the first five characters of s1.
Base Cases
The base cases are straightforward.
If s2 is empty, there is exactly one subsequence that matches it: the empty subsequence.
Therefore:
dp[i][0] = 1
for every i.
If s1 is empty while s2 is not, there is no way to form s2.
Hence:
dp[0][j] = 0
for every j > 0.
State Transition
Now consider processing the current character of s1.
If we decide not to use the current character, the answer remains the same as before.
dp[i][j] = dp[i-1][j]
If the current characters match:
s1.charAt(i-1) == s2.charAt(j-1)
then we gain one more option.
We can include this character and combine it with all the ways of forming the previous part of s2.
So:
dp[i][j] += dp[i-1][j-1]
Combining both cases gives the transition:
dp[i][j] = dp[i-1][j];
if (s1[i-1] == s2[j-1])
dp[i][j] += dp[i-1][j-1];
Since the answer can become very large, every operation is performed modulo 1000000007.
Java Implementation
class Solution {
static final int MOD = 1000000007;
public static int countWays(String s1, String s2) {
int n = s1.length();
int m = s2.length();
long[][] dp = new long[n + 1][m + 1];
// Empty string can always be formed
for (int i = 0; i <= n; i++) {
dp[i][0] = 1;
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
// Ignore current character
dp[i][j] = dp[i - 1][j];
// Include current character if it matches
if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
dp[i][j] = (dp[i][j] + dp[i - 1][j - 1]) % MOD;
}
}
}
return (int) dp[n][m];
}
}
Dry Run Example
Let's understand the algorithm with the example:
s1 = "abcabc"
s2 = "abc"
Initially:
dp[i][0] = 1
because an empty string can always be formed.
While scanning each character of s1, we either skip it or use it if it matches the current character of s2.
When the first 'a' is found, it contributes to forming "a".
When the first 'b' is found after that, it extends every existing "a" subsequence to "ab".
Similarly, every matching 'c' extends "ab" into "abc".
Later occurrences of 'a', 'b', and 'c' create additional combinations, and DP automatically counts all of them without generating every subsequence explicitly.
The final value stored in:
dp[n][m]
is the total number of matching subsequences.
Complexity Analysis
Time Complexity
O(n × m)
because each DP cell is computed exactly once.
Space Complexity
O(n × m)
for storing the DP table.
Summary
Generating all subsequences is infeasible because the number of subsequences grows exponentially. Dynamic Programming avoids this by counting valid subsequences incrementally. By defining dp[i][j] as the number of ways to form the first j characters of s2 using the first i characters of s1, we can efficiently compute the answer in O(n × m) time. This is the standard and optimal DP approach for counting matching subsequences when string lengths can be as large as 1000.