LeetCode 392: Is Subsequence

Problem Description

Given two strings s and t, determine if s is a subsequence of t. A subsequence is a sequence that can be derived from another sequence by deleting some or no characters without changing the order of the remaining characters.

Dynamic Programming Solution

This problem can be solved using dynamic programming where we build a table representing the length of the longest common subsequence between prefixes of s and t.

State Definition

Define dp[i][j] as the length of the longest common subsequence between s[0..i-1] and t[0..j-1].

Transition Logic

• When s[i-1] == t[j-1]: We found a matching character, so dp[i][j] = dp[i-1][j-1] + 1
• When characters don't match: We need to skip a character from either string, so dp[i][j] = max(dp[i-1][j], dp[i][j-1])

The latter case represents deleting either the current character from s or the current character from t.

Implementation

class Solution {
    public boolean isSubsequence(String source, String target) {
        int sourceLength = source.length();
        int targetLength = target.length();
        
        int[][] dp = new int[sourceLength + 1][targetLength + 1];
        
        for (int i = 1; i <= sourceLength; i++) {
            for (int j = 1; j <= targetLength; j++) {
                if (source.charAt(i - 1) == target.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        
        return dp[sourceLength][targetLength] == sourceLength;
    }
}

Complexity Analysis:

• Time Complexity: O(n × m)
• Space Complexity: O(n × m)

---

LeetCode 115: Distinct Subsequences

Problem Description

Given two strings s and t, count the number of distinct subsequences of s that equal t. Since the answer can be very large, return it modulo 10^9 + 7.

Dynamic Programming Solution

State Definition

Define dp[i][j] as the number of distinct subsequences in s[0..i-1] that equal t[0..j-1].

Transition Logic

When s[i-1] == t[j-1], we have two options:

1. Use s[i-1] to match t[j-1]: This gives us dp[i-1][j-1] ways
2. Skip s[i-1] and look for t[j-1] in earlier characters: This gives us dp[i-1][j] ways

So: dp[i][j] = dp[i-1][j-1] + dp[i-1][j]

When characters don't match, we can only skip s[i-1]: dp[i][j] = dp[i-1][j]

Initialization

The first row dp[i][0] should be 1 for all i because an empty string is a subsequence of any string.

Implementation

class Solution {
    public int numDistinct(String source, String pattern) {
        if (source.length() < pattern.length()) {
            return 0;
        }
        
        int sourceLength = source.length();
        int patternLength = pattern.length();
        
        int[][] dp = new int[sourceLength + 1][patternLength + 1];
        
        // Initialize: empty pattern is subsequence of any prefix
        for (int i = 0; i <= sourceLength; i++) {
            dp[i][0] = 1;
        }
        
        for (int i = 1; i <= sourceLength; i++) {
            for (int j = 1; j <= patternLength; j++) {
                if (source.charAt(i - 1) == pattern.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
                } else {
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }
        
        return dp[sourceLength][patternLength];
    }
}

Space-Optimized Solution

Since each row only depends on the previous row, we can reduce space complexity:

class Solution {
    public int numDistinct(String source, String pattern) {
        int sourceLength = source.length();
        int patternLength = pattern.length();
        
        int[] dp = new int[patternLength + 1];
        dp[0] = 1;
        
        for (int i = 1; i <= sourceLength; i++) {
            for (int j = patternLength; j > 0; j--) {
                if (source.charAt(i - 1) == pattern.charAt(j - 1)) {
                    dp[j] = dp[j] + dp[j - 1];
                }
            }
        }
        
        return dp[patternLength];
    }
}

Complexity Analysis:

• Time Complexity: O(n × m)
• Space Complexity: O(n × m) or O(m) with optimization

---

Key Insights

Both problems establish a foundation for understanding edit distance problems. The first problem checks for subsequence existence using a longest common subsequence approach, while the second counts all possible ways to match subseuqences, requiring consideration of both using and skipping each character.