Finding the number of distinct subsequences of a string is a fascinating problem with applications in bioinformatics, text processing, and more. In this article, we'll delve into the concept, a dynamic programming approach to solve it efficiently, and demonstrate the solution with examples.

Understanding Subsequences

A subsequence is a sequence derived from another sequence by removing some elements (can be none) without changing the order of the remaining elements. For example, the string "abc" has the subsequences: "", "a", "b", "c", "ab", "ac", "bc", "abc".

Problem Definition

Given a string `S`, find the number of distinct subsequences it can generate.

Solution Approach

Dynamic Programming

A dynamic programming approach leverages breaking down the problem into smaller, manageable subproblems. We use a one-dimensional array `dp` where `dp[i]` represents the number of distinct subsequences that can be formed using the first `i` characters of `S`.

Algorithm

1. Initialize DP Array: • Create a DP array of size `n+1` (where `n` is the length of the string `S`) initialized to zero. Set `dp[0] = 1` because the empty subsequence is always a valid subsequence.
2. Keep Track of the Last Occurrence: • Maintain a dictionary `last_occurrence` to store the last occurrence index of each character.
3. DP Transition: • For each character `S[i]` (1-indexed for simplicity), calculate the number of subsequences:

$$dp[i] = 2 \times dp[i-1]$$

• If the character `S[i]` has appeared before at `last_occurrence[S[i]] = j`: $$dp[i] = dp[i] - dp[j-1]$$ • Finally, update `last_occurrence[S[i]] = i`.

1. Return the Result: • `dp[n]` holds the number of distinct subsequences.

Example

Consider the string `S = "abc"`:

• Initialize: `dp = [1, 0, 0, 0]` and `last_occurrence` as an empty dictionary. • Iterating over `S`: • For `i = 1` (character 'a'): • `dp[1] = 2 * dp[0] = 2 * 1 = 2` • Update `last_occurrence = {'a': 1}` • For `i = 2` (character 'b'): • `dp[2] = 2 * dp[1] = 2 * 2 = 4` • Update `last_occurrence = {'a': 1, 'b': 2}` • For `i = 3` (character 'c'): • `dp[3] = 2 * dp[2] = 2 * 4 = 8` • Update `last_occurrence = {'a': 1, 'b': 2, 'c': 3}`

Finally, `dp[3] = 8` indicates there are 8 distinct subsequences of "abc".

Complexity Analysis

• Time Complexity: $O(n)$, where `n` is the length of string `S`. This is due to the single pass over `S` and constant-time operations on the `last_occurrence` dictionary. • Space Complexity: $O(n)$ due to the `dp` array and space for managing `last_occurrence`.

Key Points

Here is a table summarizing key steps:

Conclusion

Finding the number of distinct subsequences in a string is effectively solved using a dynamic programming approach, leveraging memoization and careful handling of repeated characters. This problem highlights the power of using a systematic method to address the combinatorial explosion in subsequence calculations.