Count Unique Subsequences

Hard

A subsequence of a string is what remains after deleting some of its characters (possibly none) without reordering the rest. For example, "ace" is a subsequence of "abcde", while "aec" is not. Given a string letters, count how many **different non-empty** strings appear among its subsequences. The answer can be huge, so return it modulo 10⁹ + 7.

Example 1

letters="xyz" → 7

All 7 non-empty subsequences are different: x, y, z, xy, xz, yz, xyz.

Example 2

letters="pop" → 6

The distinct ones are p, o, po, pp, op, pop, six in total ("p" can be picked in two ways but counts once).

Example 3

letters="bbbb" → 4

Constraints

1 ≤ len(letters) ≤ 2000
letters consists of lowercase English letters

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

String Dynamic Programming

Similar problems

Pattern With Dot and Star Hard Longest Balanced Bracket Stretch Hard Does the Text Fit the Pattern Hard Shuffle by Cutting and Swapping Hard Ways to Cross Out Hard

Input

letters="xyz"

Expected

Run checks the first 3 tests in your browser. Submit checks all 56 tests on the server, hidden ones included.