Find the number of occurrences of a subsequence in a string
Master System Design with Codemia
Enhance your system design skills with over 120 practice problems, detailed solutions, and hands-on exercises.
Introduction
Finding the number of occurrences of a subsequence within a string is a common problem in computer science, especially relevant in fields such as bioinformatics, text processing, and coding theory. Unlike substrings, which are contiguous sequences of characters, subsequences maintain the order of characters but do not require contiguity. This article will delve into the technicalities of finding the occurrences of a subsequence in a string, exploring various methods and examples to solidify understanding.
Problem Definition
Given a string `S` and a subsequence `T`, the task is to count how many distinct occurrences of `T` exist as a subsequence within `S`.
Example
Consider `S = "ababc"` and `T = "abc"`. The subsequence "abc" appears twice in "ababc":
- `S[0] = 'a'`, `S[1] = 'b'`, `S[3] = 'c'`
- `S[0] = 'a'`, `S[2] = 'b'`, `S[3] = 'c'`
Method: Dynamic Programming
Dynamic programming provides an efficient way to solve this problem by breaking it down into subproblems. Let's define a 2D table `dp` where `dp[i][j]` represents the number of times the subsequence `T[0...j-1]` appears in the string `S[0...i-1]`.
Steps & Formula
- Initialization:
- `dp[0][0]` is initialized to 1 since an empty subsequence is a subsequence of any string.
- For `i >= 1`, `dp[i][0]` is also initialized to 1 for the same reason.
- Filling the Table:
- For each character `i` in `S` and each character `j` in `T`:
- If `S[i-1]` matches `T[j-1]`:
- Otherwise:
- Result: The value at `dp[m][n]` gives the required count of subsequences where `m` and `n` are lengths of `S` and `T` respectively.
Detailed Example
Let `S = "rabbbit"` and `T = "rabbit"`. Here's how the table is filled:
| i\j | 0 | 1 ('r') | 2 ('a') | 3 ('b') | 4 ('b') | 5 ('i') | 6 ('t') |
| 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 |
| 2 | 1 | 1 | 0 | 0 | 0 | 0 | 0 |
| 3 | 1 | 1 | 1 | 0 | 0 | 0 | 0 |
| 4 | 1 | 1 | 1 | 1 | 0 | 0 | 0 |
| 5 | 1 | 1 | 1 | 2 | 1 | 0 | 0 |
| 6 | 1 | 1 | 1 | 2 | 3 | 0 | 0 |
| 7 | 1 | 1 | 1 | 2 | 3 | 3 | 0 |
| 8 | 1 | 1 | 1 | 2 | 3 | 3 | 3 |
The entry at `dp[8][6]` (bottom-right corner) is 3, reflecting the number of ways to form "rabbit" from "rabbbit".
Complexity Analysis
- Time Complexity: The dynamic programming approach has a time complexity of where `m` and `n` are the lengths of `S` and `T` respectively.
- Space Complexity: The space complexity is also due to the dp table. However, optimizations can reduce this to by keeping only the current and previous rows.
Other Techniques
Recursion with Memoization
A recursive solution involves exploring all subsequences by including or excluding the current character, using memoization to cache results and avoid redundant calculations.
Combinatorial Techniques
If `S` and `T` are small enough, combinatorial approaches using bit masking can enumerate all subsequences, but these are rarely practical for larger inputs.
Conclusion
The dynamic programming approach provides a robust and efficient method for solving the problem of counting subsequences. Understanding the breakdown and construction of the `dp` table allows for handling larger strings and more complex subsequences efficiently. The application of this technique spans a variety of problems beyond the simple counting of subsequences, offering insights into string matching and alignment tasks. For practical implementations, careful consideration of time and space optimizations is essential.
