Back to Miscellaneous Coding
Q1Question 1 of 52

Distinct Subsequences: count occurrences of t as a subsequence of s

Key Concepts
  • Define dp[i][j] as the number of ways the first i characters of s form the first j characters of t.
  • When s[i-1] == t[j-1], dp[i][j] = dp[i-1][j-1] (use it) + dp[i-1][j] (skip it).
  • When characters differ, dp[i][j] = dp[i-1][j] (skip only).
  • Base case: dp[i][0] = 1 for all i, because the empty target is always matchable once.
  • Space reduces from O(m*n) to O(n) by iterating j from high to low on a single row.
  • Counts can overflow int on large inputs, so use long or modular arithmetic in production.

Definition

Match: use + skip (diagonal + above); mismatch: skip only (above). dp[i][0] = 1.
  • Distinct Subsequences – count the number of ways to delete characters from string s to produce string t.
  • DP definition – dp[i][j] is the number of ways the first i characters of s form the first j characters of t.
  • Match transition – dp[i][j] = dp[i-1][j-1] + dp[i-1][j] (use the character or skip it).
  • Mismatch transition – dp[i][j] = dp[i-1][j] (can only skip).
  • Base case – dp[i][0] = 1 for all i; the empty target is matchable exactly once.
  • Complexity – O(m * n) time, O(n) space with a single row.

At the National Bank of India, a pattern-counter counts how many times a short approval code appears as an ordered subsequence inside a long audit log. At each log character matching the next code character, Priya either uses it or skips it, adding both counts.

Understanding the Concepts

What is the Distinct Subsequences problem?

Given strings s (source) and t (target), count the number of distinct subsequences of s that equal t. A subsequence is formed by deleting zero or more characters from s without changing the order of the remaining characters. This is a counting DP problem.

JAVA
package com.bank.service;

public class DistinctSubsequences {
    public long numDistinct(String s, String t) {
        int m = s.length(), n = t.length();
        long[] dp = new long[n + 1];
        dp[0] = 1;
        for (int i = 1; i <= m; i++) {
            for (int j = n; j >= 1; j--) {
                if (s.charAt(i - 1) == t.charAt(j - 1)) {
                    dp[j] += dp[j - 1];
                }
            }
        }
        return dp[n];
    }
}

How does the DP recurrence work?

At each position in s, we decide whether to use the current character to match the current position in t, or skip it. If s[i-1] equals t[j-1], we have two choices: use it (contributing dp[i-1][j-1]) or skip it (contributing dp[i-1][j]). If they differ, we can only skip.

JAVA
package com.bank.service;

public class RecurrenceDemo {
    public static void main(String[] args) {
        String s = "rabbbit", t = "rabbit";
        int m = s.length(), n = t.length();
        long[][] dp = new long[m + 1][n + 1];
        for (int i = 0; i <= m; i++) dp[i][0] = 1;
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (s.charAt(i - 1) == t.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
                } else {
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }
        System.out.println("Count: " + dp[m][n]); // 3
    }
}
TEXT
Count: 3

Why is dp[i][0] = 1?

The empty target string can always be formed from any prefix of s in exactly one way: by taking no characters. This is the base case that seeds the first column of the DP table.

JAVA
// dp[0][0] = 1: empty s matches empty t in 1 way
// dp[5][0] = 1: first 5 chars of s match empty t in 1 way
// dp[0][3] = 0: empty s cannot form non-empty t
for (int i = 0; i <= m; i++) dp[i][0] = 1;
for (int j = 1; j <= n; j++) dp[0][j] = 0; // implicit

How does the space optimisation work?

Since each row depends only on the previous row, we use a single array of size n+1. The critical detail is iterating j from high to low, so that dp[j-1] still holds the previous row's value when we read it (it has not been updated yet in this iteration).

JAVA
package com.bank.service;

public class SpaceOptimised {
    public long numDistinct(String s, String t) {
        int n = t.length();
        long[] dp = new long[n + 1];
        dp[0] = 1;
        for (int i = 0; i < s.length(); i++) {
            // Iterate RIGHT to LEFT to preserve previous row values
            for (int j = n; j >= 1; j--) {
                if (s.charAt(i) == t.charAt(j - 1)) {
                    dp[j] += dp[j - 1]; // dp[j-1] is still from previous row
                }
            }
        }
        return dp[n];
    }
}

What is the time and space complexity?

The DP table has m * n cells, each computed in O(1). The space-optimised version uses a single row of size n+1.

  • Time – O(m * n) where m = len(s), n = len(t).
  • Space – O(n) with the single-row optimisation.
  • Overflow – counts can be very large; use long or modular arithmetic.
JAVA
// Full table: O(m*n) time, O(m*n) space
long[][] dp = new long[m + 1][n + 1];

// Optimised: O(m*n) time, O(n) space
long[] dp = new long[n + 1];
// Iterate j from n down to 1

What are the edge cases?

Edge cases include t longer than s (answer is 0), t empty (answer is 1), s and t identical (answer is 1), and both empty (answer is 1).

JAVA
package com.bank.service;

public class SubseqEdgeCases {
    public static void main(String[] args) {
        DistinctSubsequences ds = new DistinctSubsequences();
        System.out.println(ds.numDistinct("abc", "abcd")); // 0 (t longer)
        System.out.println(ds.numDistinct("abc", ""));      // 1 (t empty)
        System.out.println(ds.numDistinct("abc", "abc"));   // 1 (identical)
        System.out.println(ds.numDistinct("", ""));         // 1 (both empty)
    }
}
TEXT
0
1
1
1

What are common mistakes?

The most common mistake in the space-optimised version is iterating j from low to high instead of high to low, which overwrites dp[j-1] before it is read. Another mistake is using int instead of long for the counts.

JAVA
// WRONG: left to right overwrites dp[j-1] too early
for (int j = 1; j <= n; j++) {
    if (s.charAt(i) == t.charAt(j - 1))
        dp[j] += dp[j - 1]; // dp[j-1] already updated!
}

// CORRECT: right to left preserves dp[j-1]
for (int j = n; j >= 1; j--) {
    if (s.charAt(i) == t.charAt(j - 1))
        dp[j] += dp[j - 1]; // dp[j-1] still from previous row
}

How would you apply this in a banking system?

At the National Bank of India, an audit tool counts how many times a short approval code appears as an ordered subsequence within a long transaction log, to gauge how many potential approval chains exist. The counts can be extremely large, so the system uses long types.

JAVA
package com.bank.service;

public class AuditSubsequenceCounter {
    public long countApprovalChains(String transactionLog, String approvalCode) {
        int m = transactionLog.length();
        int n = approvalCode.length();
        long[] dp = new long[n + 1];
        dp[0] = 1;
        for (int i = 0; i < m; i++) {
            for (int j = n; j >= 1; j--) {
                if (transactionLog.charAt(i) == approvalCode.charAt(j - 1)) {
                    dp[j] += dp[j - 1];
                }
            }
        }
        return dp[n];
    }
}

What should a senior engineer know?

A senior engineer should recognise that this is a counting variant of the longest common subsequence (LCS) family. Unlike LCS which maximises length, this counts all matches. They should also know that for very long strings, the counts can overflow even long, requiring modular arithmetic with a prime modulus.

JAVA
// Modular arithmetic for very large counts:
long MOD = 1_000_000_007;
if (s.charAt(i) == t.charAt(j - 1)) {
    dp[j] = (dp[j] + dp[j - 1]) % MOD;
}

Visual Overview

DIAGRAM
Example: s = "rabbbit", t = "rabbit"

     ""  r  a  b  b  i  t
 ""   1  0  0  0  0  0  0
  r   1  1  0  0  0  0  0
  a   1  1  1  0  0  0  0
  b   1  1  1  1  0  0  0
  b   1  1  1  2  1  0  0
  b   1  1  1  3  3  0  0
  i   1  1  1  3  3  3  0
  t   1  1  1  3  3  3  3  ← answer

Match: dp[i][j] = dp[i-1][j-1] + dp[i-1][j]
  (use character)    (skip character)

Mismatch: dp[i][j] = dp[i-1][j]
  (skip only)

The 3 distinct subsequences of "rabbbit" that form "rabbit":
  r a b b i t  (using b at index 2 and 3)
  r a b b i t  (using b at index 2 and 4)
  r a b b i t  (using b at index 3 and 4)

Key Takeaway

Distinct Subsequences is a two-dimensional counting DP. I define dp[i][j] as the number of ways the first i characters of the source form the first j characters of the target. The base case is dp[i][0] = 1 for all i, because the empty target is always matchable once.

When the current source character matches the current target character, I have two choices: use it (contributing the diagonal cell) or skip it (contributing the cell above). When they differ, I can only skip. The answer is dp[m][n]. The space-optimised version uses a single row iterated right to left.

The critical implementation detail is the iteration direction: right to left in the space-optimised version preserves the previous row's values. The common mistake is iterating left to right, which overwrites dp[j-1] before it is read. Counts can overflow int on large inputs, so use long.

At the National Bank of India, an audit tool counted how many times a short approval code appeared as an ordered subsequence in a long transaction log, gauging the number of potential approval chains.

Remember one sentence: match means use-plus-skip from the diagonal and above; mismatch means skip-only from above.

---

Share
Use ← → arrow keys to navigate