Standard Bar Recursion · Subsequences Pattern O(2^n) enumeration in the source; O(n^2) set-of-subsequence-ends or O(n * alphabet) DP exists · O(2^n) for the pattern set in the source
A genomics archive stores each sample as a lowercase string, and the audit asks how many distinct reading patterns can be formed by deleting arbitrary characters while preserving order — the empty pattern included. Duplicated letters mean different deletion choices can yield the same pattern, so the counter must collect the patterns in a set rather than tallying every branch. The report carries the distinct-pattern count modulo 10^9 + 7.
Input: A string s of lowercase English letters.
Output: The number of distinct subsequences of s (empty included), modulo 10^9 + 7.
1 <= s.length <= 20 (exponential search; DP handles much larger inputs)s consists of lowercase English lettersInput: {"s":"gfg"}
Output: 7
The distinct patterns are "", "g", "f", "gf", "fg", "gg", and "gfg" — the two g branches collapse.
Input: {"s":"ab"}
Output: 4
"", "a", "b", "ab" — with distinct letters every deletion choice is unique.