Distinct Subsequences
DP on Strings DSA practice problem on Onlearn.
Difficulty: hard.
Topics: Counting the number of distinct subsequences of one string within another (Distinct Subsequences Problem), Dynamic Programming, Memoization, Tabulation, Space Optimization, Recursion, Strings, Subsequences, Time Complexity, Space Complexity, Modulo Arithmetic, Base Cases, Overlapping Subproblems, Optimal Substructure, dynamic programming, memoization, tabulation, space optimization, recursion, time complexity analysis.
Distinct Subsequences Problem Statement Given two strings S1 and S2, find the number of distinct subsequences of S1 that are equal to S2. A subsequence of a string is a new string formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (For example, "ace" is a subsequence of "abcde" while "aec" is not). Since the answer can be very large, return it modulo 10^9 + 7. Input Specification The input consists of two lines: The first line contains string S1. The second line contains string S2. Output Specification Print a single integer, the number of distinct subsequences of S1 that are equal to S2, modulo 10^9 + 7. Constraints 1 <= len(S2) <= len(S1) <= 5000 S1 and S2 consist of lowercase English letters. Sample Test Case Input: Output: Explanation: The distinct subsequences of "babgbag" that are equal to "bag" are: 1. b a b g bag 2. ba b gb ag 3. bab g ba g 4. bab g b a g 5. b a bg b a g