FindSubsequence
Logical Breakdown
- [ ] Subproblem Identification:
- [ ] Optimal Substructure:
- [ ] Constraint Handling: (e.g., Modulo \(10^9 + 7\))
- [ ] Optimization: (Matrix Exponentiation if 'A' is huge)
Mathematical Rigor
State Definition
Let \(dp[i]\) be the state for the \(i\)-th subproblem.
Recurrence Relation
Visualization
Complexity Analysis
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Iterative DP | \(O(N)\) | \(O(1)\) |
Code Reference
package com.dsa.recursion;
import java.util.*;
/
* Problem: FindSubsequence
* Group: 07. Recursion
*/
/
* ============================================================================================
* PROBLEM: Find Subsequence
* ============================================================================================
*
* ---------------------
* 1. Problem Description
* ---------------------
* Given two strings A and B, determine if A is a subsequence of B.
* Return "YES" if it is, otherwise return "NO".
*
* Definition:
* String A is a subsequence of B if A can be obtained from B by deleting zero or more
* characters from B without changing the relative order of the remaining characters.
*
* ---------------------
* 2. Logical Breakdown & Mathematical Formulation
* ---------------------
* Let N = length(A) and M = length(B).
* We need to find indices \(idx_1, idx_2, ..., idx_N\) in B such that:
* 1. \(B[idx_k] == A[k]\) for all \(0 \le k < N\)
* 2. \(idx_1 < idx_2 < ... < idx_N\) (Strictly increasing indices)
*
* Algorithm (Two Pointers):
* We maintain two pointers:
* - i pointing to the current character in A (Target).
* - j pointing to the current character in B (Source).
*
* Traversal Rule:
* 1. Iterate through B using j.
* 2. If \(A[i] == B[j]\), it means we found the current required character. Increment i to look for the next one.
* 3. Regardless of a match, increment j to proceed to the next character in B.
*
* Termination Condition:
* - If i reaches length(A), we successfully found all characters in order. Return "YES".
* - If j finishes iterating B and i < length(A), we failed. Return "NO".
*
* ---------------------
* 3. Constraints & Complexity Analysis
* ---------------------
* Constraints:
* 1 <= |A|, |B| <= 100,000
* Characters are lowercase English letters ('a' - 'z').
*
* Time Complexity:
* O(|B|) - We traverse the source string B at most once.
* The pointer i moves only when j moves, so operations are strictly linear.
*
* Space Complexity:
* O(1) - We use only two integer variables for pointers.
*
* ---------------------
* 4. Input / Output Format
* ---------------------
* Input:
* - String A (The subsequence to search for).
* - String B (The source string).
*
* Output:
* - String "YES" or "NO".
*
* ---------------------
* 5. Examples
* ---------------------
* Input 1: A = "bit", B = "dfbkjijgbbiihbmmt"
* Execution:
* - Find 'b': Found at B[2]. (i=1)
* - Find 'i': Found at B[5]. (i=2)
* - Find 't': Found at B[16]. (i=3)
* - i == len(A) -> YES
*
* Input 2: A = "apple", B = "appel"
* Execution:
* - Match 'a', 'p', 'p'.
* - Next needed: 'l'. Current B char: 'e' (mismatch).
* - Next B char: 'l'. Match 'l'.
* - Next needed: 'e'. End of B reached.
* - Result -> NO (Order violation).
*
* ============================================================================================
*/
public class FindSubsequence {
public int solve(String A, String B) {
// TODO: Implement solution
return 0;
}
}