Problem Statement
DNA Sequence Matcher
You're a bioinformatics researcher analyzing DNA sequences. You have a source sequence S and a target sequence T, and you need to determine how many distinct ways you can extract the target sequence from the source sequence.
A subsequence is formed by removing some characters from the original string without changing the order of the remaining characters. For example, "ACE" is a subsequence of "ABCDE", while "AEC" is not.
Your task is to count the number of distinct subsequences of S that are equal to T.
For example, if S = "AAGCTAGCT" and T = "AGT", you need to find how many different ways you can extract "AGT" from "AAGCTAGCT" by deleting some characters.
Examples
Example 1:
Input: S = "rabbbit", T = "rabbit"
Output: 3
Explanation: There are 3 ways to extract "rabbit" from "rabbbit":
1. ra(b)bbit → rabbit (remove the 1st 'b')
2. rab(b)bit → rabbit (remove the 2nd 'b')
3. rabb(b)it → rabbit (remove the 3rd 'b')
Example 2:
Input: S = "babgbag", T = "bag"
Output: 5
Explanation: There are 5 ways to extract "bag" from "babgbag":
1. (ba)bgbag → bag (use 1st 'b', 1st 'a', 1st 'g')
2. (ba)bgba(g) → bag (use 1st 'b', 1st 'a', 2nd 'g')
3. (b)abgb(ag) → bag (use 1st 'b', 2nd 'a', 2nd 'g')
4. ba(b)gb(ag) → bag (use 2nd 'b', 2nd 'a', 2nd 'g')
5. babg(bag) → bag (use 3rd 'b', 2nd 'a', 2nd 'g')
Constraints
- 1 <= S.length, T.length <= 1000
- S and T consist of uppercase and lowercase English letters
- The answer is guaranteed to fit in a 32-bit signed integer
Problem Breakdown
To solve this problem, we need to:
- The order of characters matters in subsequences
- We need to count all possible ways to form T from S by deleting characters
- This problem has optimal substructure, making it suitable for dynamic programming
- When we encounter a matching character, we have two choices: use it or skip it
- The total number of ways is the sum of ways from all valid choices
- We can build our solution incrementally by considering one character at a time
String Problems
Learning Objective
Apply string manipulation concepts to solve a real-world problem.
DNA Sequence Matcher
You're a bioinformatics researcher analyzing DNA sequences. You have a source sequence S and a target sequence T, and you need to determine how many distinct ways you can extract the target sequence from the source sequence.
A subsequence is formed by removing some characters from the original string without changing the order of the remaining characters. For example, "ACE" is a subsequence of "ABCDE", while "AEC" is not.
Your task is to count the number of distinct subsequences of S that are equal to T.
For example, if S = "AAGCTAGCT" and T = "AGT", you need to find how many different ways you can extract "AGT" from "AAGCTAGCT" by deleting some characters.
Examples
Example 1:
There are 3 ways to extract "rabbit" from "rabbbit": 1. ra(b)bbit → rabbit (remove the 1st 'b') 2. rab(b)bit → rabbit (remove the 2nd 'b') 3. rabb(b)it → rabbit (remove the 3rd 'b')
Example 2:
There are 5 ways to extract "bag" from "babgbag": 1. (ba)bgbag → bag (use 1st 'b', 1st 'a', 1st 'g') 2. (ba)bgba(g) → bag (use 1st 'b', 1st 'a', 2nd 'g') 3. (b)abgb(ag) → bag (use 1st 'b', 2nd 'a', 2nd 'g') 4. ba(b)gb(ag) → bag (use 2nd 'b', 2nd 'a', 2nd 'g') 5. babg(bag) → bag (use 3rd 'b', 2nd 'a', 2nd 'g')
Problem Breakdown
Constraints:
- 1 <= S.length, T.length <= 1000
- S and T consist of uppercase and lowercase English letters
- The answer is guaranteed to fit in a 32-bit signed integer
Key Insights:
The order of characters matters in subsequences
We need to count all possible ways to form T from S by deleting characters
This problem has optimal substructure, making it suitable for dynamic programming
When we encounter a matching character, we have two choices: use it or skip it
The total number of ways is the sum of ways from all valid choices
We can build our solution incrementally by considering one character at a time
Real-World Application
This problem has several practical applications:
Bioinformatics
Analyzing DNA sequences and finding patterns in genetic data.
Text Processing
Searching for patterns in text documents while allowing for variations.
Database Query Matching
Implementing fuzzy search algorithms in database systems.
Natural Language Processing
Analyzing text patterns and relationships between words in different contexts.