LCS and Subsequence Problems
Here is the converted text from the image:
Longest Common Subsequence
1. Largest Common Substring
2. Print LCS
3. Shortest Common Supersequence
4. Print SCS
5. Min. # of insertion and deletion a → b
6. Largest Repeating Subsequence
7. Length of largest subsequence of a word is a substring of b
8. Subsequence Pattern Matching
9. Count how many times a appears as subsequence in b
10. Largest Palindromic Subsequence
11. Largest Palindromic Substring
12. Count of Palindromic Substring
13. Min # of deletions in a string to make it a palindrome
14. Min # of insertions in a string to make it a palindrome
Let me know if you want explanations or solutions for any of these problems!
This is a concept note for Longest Common Subsequence (LCS) problem, illustrated with an
example and approach breakdown. Let's break this down in simple steps and then
implement JavaScript code for LCS.
1/9
📌 Understanding the Diagram:
Problem:
Find Longest Common Subsequence (LCS) of two strings x and y .
Example:
ini
x = "abcdgh"
y = "abedfhr"
LCS = "abdh" (length = 4)
1. Step-by-step Explanation:
A) Inputs:
x : "abcdgh"
y : "abedfhr"
B) Output:
LCS: "abdh"
Length: 4
2. Approach Recap:
Recursion Base Cases:
If any string is empty, LCS is 0.
Recursive Relation:
If last characters match: 1 + LCS(x-1, y-1)
Else: max(LCS(x-1, y), LCS(x, y-1))
2/9
3. Flow to Solve:
mathematica
1. Problem Statement
2. Recursive Discussion (Find recursive relation)
3. Base Cases
4. DP Table (Bottom-Up)
5. Print LCS
4. Visualization in Matrix:
Fill table based on matches:
css
a b e d f h r
a 1 1 1 1 1 1 1
b 1 2 2 2 2 2 2
c 1 2 2 2 2 2 2
d 1 2 2 3 3 3 3
g 1 2 2 3 3 3 3
h 1 2 2 3 3 4 4
Backtrack to get the sequence.
✅ JavaScript Solution for LCS
A) Length of LCS
javascript
function lcsLength(x, y) {
const m = [Link];
const n = [Link];
3/9
const dp = [Link]({ length: m + 1 }, () => Array(n + 1).fill(0));
for (let i = 1; i <= m; i++) {
for (let j = 1; j <= n; j++) {
if (x[i - 1] === y[j - 1]) {
dp[i][j] = 1 + dp[i - 1][j - 1];
} else {
dp[i][j] = [Link](dp[i - 1][j], dp[i][j - 1]);
}
}
}
return dp[m][n];
}
const x = "abcdgh";
const y = "abedfhr";
[Link]("Length of LCS:", lcsLength(x, y)); // Output: 4
B) Print LCS String
javascript
function printLCS(x, y) {
const m = [Link];
const n = [Link];
const dp = [Link]({ length: m + 1 }, () => Array(n + 1).fill(0));
// Fill DP table
for (let i = 1; i <= m; i++) {
for (let j = 1; j <= n; j++) {
if (x[i - 1] === y[j - 1]) {
dp[i][j] = 1 + dp[i - 1][j - 1];
} else {
dp[i][j] = [Link](dp[i - 1][j], dp[i][j - 1]);
}
}
}
4/9
// Backtracking to find LCS
let i = m, j = n;
let lcsStr = [];
while (i > 0 && j > 0) {
if (x[i - 1] === y[j - 1]) {
[Link](x[i - 1]);
i--;
j--;
} else if (dp[i - 1][j] > dp[i][j - 1]) {
i--;
} else {
j--;
}
}
return [Link]().join('');
}
const x1 = "abcdgh";
const y1 = "abedfhr";
[Link]("LCS:", printLCS(x1, y1)); // Output: "abdh"
✅ Summary of Flow:
Step Description
Problem Find LCS
Recursive Discussion Explore recursive relation
Base Case If any string is empty, return 0
DP Table Fill bottom-up to avoid recomputation
Backtrack Extract actual LCS string from table
Output Print Length & String
5/9
💡 Important Notes:
Recursion helps understand problem flow (Top-down).
DP Table gives optimized solution (Bottom-up).
Backtrack gives the LCS string itself.
Can also modify for variations like printing all LCS, counting number of LCS, shortest
common supersequence, etc.
If you want, I can also explain recursive to DP conversion step-by-step, or how to handle
LCS variants. Want that? 🚀
Great! Let's now explain the recursive approach of LCS step by step and add it properly to
your document.
✅ Recursive Approach of LCS
💡 Idea:
We solve the Longest Common Subsequence (LCS) problem using recursion by comparing
characters of the two strings from the end and making decisions based on whether they
match or not.
📌 Recursive Formula:
Case 1: Characters Match
If the last characters of both strings match, we include this character in LCS and recursively
solve for the remaining strings.
6/9
LCS(x, y, m, n) = 1 + LCS(x, y, m-1, n-1)
Case 2: Characters Don't Match
If the last characters do not match, we skip one character either from x or y and take the
maximum of both options:
lua
LCS(x, y, m, n) = max(LCS(x, y, m-1, n), LCS(x, y, m, n-1))
📌 Base Case:
If either m == 0 or n == 0 , meaning any one string is empty, LCS is 0:
kotlin
if (m == 0 || n == 0) return 0;
✅ Recursive JavaScript Implementation:
javascript
function lcsRecursive(x, y, m, n) {
// Base Case: If either string is empty
if (m === 0 || n === 0) return 0;
// If last characters match, add 1 and recur for remaining
if (x[m - 1] === y[n - 1]) {
return 1 + lcsRecursive(x, y, m - 1, n - 1);
} else {
// If not match, take max of excluding one character either from x or y
return [Link](
lcsRecursive(x, y, m - 1, n),
lcsRecursive(x, y, m, n - 1)
7/9
);
}
}
// Example
const x = "abcdgh";
const y = "abedfhr";
[Link]("Length of LCS (Recursive):", lcsRecursive(x, y, [Link], [Link]));
// Output: 4
🔑 Key Points:
Concept Description
Recursive Sub-problems Break problem into smaller subproblems by removing last char
Base Case If any string is empty, return 0
Recursive Relation (Match) 1 + LCS of remaining strings
Recursive Relation (No Match) Max of LCS excluding one character
Time Complexity O(2^(m+n)) (Exponential, inefficient for large strings)
Space Complexity O(m + n) (for recursion stack)
⚠️ Drawback of Recursive Approach:
Highly inefficient for large strings due to repeated sub-problems.
Needs optimization using Dynamic Programming (DP) via memoization or tabulation.
👉 Next Step (Optional): Explain how to optimize this recursive solution using Memoization
(Top-Down DP) to avoid recomputation.
8/9
If you want, I can add Memoization version too in this document. Want me to proceed? 🚀
The memoization version has been added to the document along with a complete
explanation and code example! 🚀
If you'd like, we can now proceed to Tabulation (Bottom-Up DP) approach or explore LCS
variations like printing all LCS sequences. Let me know! 💡✨
Tabulation (Bottom-Up DP) has been successfully added to your document with full
JavaScript implementation and explanation! ✅
If you now want, we can move on to printing the actual LCS string from the DP table or
explore other variations like Shortest Common Supersequence (SCS). Let me know what
you prefer! 🚀
9/9
