Count Matching Subsequences

Problem Overview

Count how many ways s2 appears as a subsequence of s1 (not necessarily contiguous).

Intuition

Count how many ways s2 appears as a subsequence of s1 (not necessarily contiguous). Process s1 left to right: dp[j] stores match counts for prefix s2[0..j−1]. When the current s1 character equals s2[j−1], every prior way to match s2[0..j−2] can extend with this character, so add dp[j−1] to dp[j].

Algorithm

1Let n = |s1|, m = |s2|. dp[0] = 1 (empty subsequence of s2).
2For each character charS1 in s1:
3Loop j from m down to 1; if charS1 == s2[j−1]: dp[j] = (dp[j] + dp[j−1]) % MOD.
4Return dp[m] modulo 10⁹ + 7.

Example Walkthrough

Input: s1 = "rabbbit", s2 = "rabbit"

1. Three ways to pick the extra b positions among matches for rabbit.
2. Each matching s1 index choice yields one distinct subsequence alignment.

Output: 3

Common Pitfalls

• Iterate j backwards so dp[j−1] still reflects the previous s1 prefix.
• dp[j] keeps its value when characters do not match (implicit skip).
• Apply modulo on every addition — counts grow quickly.

Count Matching Subsequences.java

Java

// Approach: 1D DP — dp[j] = ways to form s2[0..j-1] as a subsequence of the s1 prefix processed so far.
// When characters match, dp[j] += dp[j-1] (take the match or skip). Iterate j backwards per s1 char.
// Time: O(n * m) Space: O(m)

class Solution {

    static int mod = 1000000007;

    public static int countWays(String s1, String s2) {
        int n = s1.length(), m = s2.length();
        // Base case: dp[0] = 1 represents an empty s2, which has 1 subsequence match
        int[] dp = new int[m + 1];
        dp[0] = 1;
        // Process s1 characters one by one
        for (int i = 1; i <= n; i++) {
            char charS1 = s1.charAt(i - 1);
            // Traverse backwards to use values from the previous 'i' iteration
            for (int j = m; j >= 1; j--) {

                if (charS1 == s2.charAt(j - 1)) {
                    dp[j] = (dp[j] + dp[j - 1]) % mod;
                }
                // 'else' condition is implicit since dp[j] keeps its previous row value
            }
        }

        return dp[m];
    }
}

Was this solution helpful?