Count Distinct Nonempty Subsequences of a Lowercase String
Company: Google
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Other
### Problem
Return the number of different nonempty strings obtainable from `s` by deleting characters while preserving the order of those retained. Equal resulting strings count once even if produced by different index choices. Return the count modulo `10^9+7`.
```cpp
class Solution {
public:
int distinctSubseqII(string s);
};
```
### Examples
**Example 1:**
```text
Input: s = "abb"
Output: 5
Explanation: The distinct nonempty subsequences are a,b,ab,bb,and abb.
```
**Example 2:**
```text
Input: s = "abcd"
Output: 15
Explanation: Every nonempty subset of the four distinct positions produces a distinct string, giving2^4-1=15.
```
### Constraints
- `1 <= s.length <= 2000`.
- s contains only lowercase English letters.
### Contract considerations
The task counts distinct strings, not combinations of selected positions.
```hint Read the boundary condition
When appending another copy of a character, identify which c-ending strings were already possible.
```
### Boundary reminders
The task counts distinct strings, not combinations of selected positions.
Overview: Count Distinct Nonempty Subsequences of a Lowercase String. Return the number of different nonempty strings obtainable from s by deleting characters while preserving the order of those retained.