Problem link ও উৎস
- **Original source:** Classic two-string alignment DP exercise
- **Platform:** LeetCode —
- **Topic:** dynamic programming (string DP)
- **Difficulty:** Medium
- **Pattern:** String DP (two-prefix state shape)
- **Basic idea inherited from:** Two-prefix state shape — দুটো string-এর prefix নিয়ে `dp[i][j]` grid, যেটা পরে Edit Distance, Regex matching-এও ফেরে
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
দুটো string `a` আর `b` দেওয়া। তোমাকে এমন একটা সবচেয়ে লম্বা subsequence খুঁজতে হবে যেটা **দুটোতেই** আছে। Subsequence মানে: original-এর character-গুলো একই order-এ রেখে কিছু character বাদ দিয়ে যা পাও — পাশাপাশি (contiguous) হওয়া লাগে না। তুমি শুধু **length** চাও।
```text
a = "abcde"
b = "ace"
সবচেয়ে লম্বা shared subsequence: "ace" -> length 3
```
### Input ও output {#8-example-input-and-output}
```text
Input : a = "abcde", b = "ace" -> Output: 3 ("ace")
Input : a = "abc", b = "abc" -> Output: 3 ("abc")
Input : a = "abc", b = "def" -> Output: 0 (কিছুই common নয়)
Edge case 1: a = "", b = "abc" -> Output: 0
Edge case 2: a = "bl", b = "yby" -> Output: 1 ("b")
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
ভাবো দুজন মানুষ আলাদা আলাদা গান শুনে একটা করে শব্দ-তালিকা লিখল। তুমি জানতে চাও সবচেয়ে লম্বা কোন শব্দ-ক্রম **দুজনের তালিকাতেই** একই order-এ পাওয়া যায় (মাঝে অন্য শব্দ থাকলেও চলবে)। প্রতিটা শব্দে দাঁড়িয়ে জিজ্ঞেস করো: "দুজনের এই মুহূর্তের শব্দ কি এক? এক হলে দুজনকেই এক ধাপ এগোও আর গোনায় ১ যোগ করো; না হলে যেকোনো একজনকে এক ধাপ এগিয়ে দেখো কে বেশি দেয়।"
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#2-which-basic-idea-does-this-inherit-from}
এটা two-prefix state shape-এর প্রথম খাঁটি প্রতিনিধি। আগের grid DP (#7 Unique Paths)-এ `dp[r][c]` ছিল একটা grid-এর cell; এখানে দুই index `i, j` দুটো **আলাদা string**-এর prefix-length মাপে। এই `dp[i][j]` কঙ্কালটাই পরে Edit Distance (#18), Regex matching (#22)-এ ব্যবহার হবে — তাই এটা ভালো করে শিখে নাও।
### ভেতরের যুক্তি {#3-what-is-the-hidden-math-or-logic}
লুকানো logic দুই string-এর শেষ character তুলনা। `a[i-1]` আর `b[j-1]` দেখো — যদি সমান হয়, সেই character দুটোকে LCS-এ জুড়ে দাও, আর বাকি প্রশ্নটা ছোট হয়ে যায় (`dp[i-1][j-1]`)। সমান না হলে অন্তত একটা শেষ character LCS-এ নেই — তাই হয় `a`-র শেষটা বাদ দাও (`dp[i-1][j]`), নয় `b`-র শেষটা বাদ দাও (`dp[i][j-1]`), যেটা বড়।
### কী দিয়ে তথ্য রাখব {#4-which-data-structure-is-needed}
একটা **2D array** `dp`, size `(m+1) x (n+1)` যেখানে `m = len(a)`, `n = len(b)`। `dp[i][j]` = `a`-র প্রথম `i` character আর `b`-র প্রথম `j` character-এর LCS-length। Row `i` শুধু row `i-1` আর একই row-এর বাঁ-cell পড়ে, তাই দুই row rolling করে O(n) space-এও করা যায়।
### এটি কেন উপযুক্ত {#5-why-this-data-structure-fits}
State-এ দুটো independent সংখ্যা লাগে — `a`-তে কতদূর এগিয়েছি, আর `b`-তে কতদূর — কারণ শেষ decision ("শেষ character দুটো কী") নিতে দুটোই জানা দরকার। দুই-dimensional index ঠিক এই দুই সংখ্যাকে ধরে। `+1` padding row/column "খালি prefix" represent করে, যাতে base case এমনিই 0 হয়ে যায়।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
প্রথম সরল চিন্তা: শেষ character তুলনা করে recurse করো।
```text
lcs(i, j): # a[0..i-1], b[0..j-1]-এর LCS length
if i == 0 or j == 0: return 0
if a[i-1] == b[j-1]:
return 1 + lcs(i-1, j-1)
return max(lcs(i-1, j), lcs(i, j-1))
answer = lcs(m, n)
```
### কোথায় বেশি কাজ হচ্ছে {#10-why-brute-force-is-slow}
mismatch হলে প্রতিটা call দুটো নতুন call জন্ম দেয় (`(i-1, j)` আর `(i, j-1)`), তাই naive recursion **O(2^(m+n))** পর্যন্ত যায়। আর একই `(i, j)` জোড়া বারবার গোনা হয় — overlapping subproblems। অথচ আলাদা `(i, j)` জোড়ার সংখ্যা মাত্র `(m+1) x (n+1)`, তাই memoize করলেই বিরাট লাভ।
### যে বিষয়টি খেয়াল করতে হবে {#11-key-observation}
মূল observation: উত্তর শুধু **দুই prefix-length** `(i, j)`-এর উপর নির্ভর করে — কোন path দিয়ে সেখানে এলাম তাতে কিছু যায় আসে না। তাই প্রতিটা `(i, j)` একবার গুনে রাখলেই হয়, exponential কাজ `O(m·n)`-এ নেমে আসে।
### আরও কম কাজে সমাধান {#12-optimized-intuition}
**State (শব্দে):** `dp[i][j]` = `a`-র প্রথম `i`-টা character আর `b`-র প্রথম `j`-টা character-এর longest common subsequence-এর length।
**Transition:**
```text
if a[i-1] == b[j-1]:
dp[i][j] = dp[i-1][j-1] + 1 # শেষ character দুটো match
else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1]) # যেকোনো একটার শেষ বাদ
```
**Base case:** `dp[0][j] = 0` আর `dp[i][0] = 0` — কোনো string খালি হলে common কিছু নেই।
**Answer location:** `dp[m][n]`।
Tabulation: padding row/column 0 দিয়ে শুরু করে, row by row (`i = 1..m`), প্রতিটা row-তে বাঁ থেকে ডানে (`j = 1..n`) ভরো। প্রতিটা cell তার diagonal, উপর আর বাঁ cell পড়ে — সবই আগে filled।
### ভাবনার পরিবর্তন {#13-thinking-tweak}
**মোচড়:** "সবচেয়ে লম্বা common অংশটা সরাসরি খুঁজব" — এই বড় প্রশ্নের বদলে শুধু **শেষ character**-এ মনোযোগ দাও। শেষ দুটো character match করলে সমস্যাটা এক ধাপ ছোট হয়; না করলে অন্তত একজনের শেষ character অকেজো, তাই তাকে ফেলে দাও। বড় সমস্যা একটা ছোট প্রশ্নে ("এই দুটো শেষ character নিয়ে কী করব") গুটিয়ে যায়।
### ছবিতে বোঝা {#7-visual-explanation}
`a = "abcde"`, `b = "ace"`। Row = `a`-র prefix, column = `b`-র prefix:
```text
"" a c e
"" 0 0 0 0
a 0 1 1 1
b 0 1 1 1
c 0 1 2 2
d 0 1 2 2
e 0 1 2 3 <- answer
rule:
if a[i-1] == b[j-1]: dp[i][j] = dp[i-1][j-1] + 1 (diagonal + 1)
else: dp[i][j] = max(dp[i-1][j], dp[i][j-1])
```
Diagonal arrow মানে match (length বাড়ল); উপর/বাঁ arrow মানে একটা character বাদ। উত্তর সবসময় নিচের-ডানের ঘরে।
### ছোট input-এ ধাপে ধাপে {#14-step-by-step-dry-run}
`a = "bl"`, `b = "yby"`, 2D table (rows = `a`, cols = `b`):
1. `dp[0][*] = 0`, `dp[*][0] = 0` (base padding)
2. i=1 (`a[0]='b'`): j=1 (`'y'`) mismatch → `max(0,0)=0`; j=2 (`'b'`) match → `dp[0][1]+1 = 0+1 = 1`; j=3 (`'y'`) mismatch → `max(dp[0][3], dp[1][2]) = max(0,1) = 1`
3. i=2 (`a[1]='l'`): সব column-এ mismatch → প্রতিটায় উপর/বাঁ-এর max বহন হয়: `dp[2] = [0,0,1,1]`
4. `dp[2][3] = 1` → answer
হাতে মিলিয়ে: একমাত্র common character `'b'`, তাই LCS length 1. ✔
## কোড ও ব্যাখ্যা {#code}
### Python {#15-python-solution}
```python
# ---- way 1: memoization (top-down) ----
def lcs_memo(a, b):
from functools import lru_cache
@lru_cache(maxsize=None)
def solve(i, j): # a[0..i-1], b[0..j-1]
if i == 0 or j == 0:
return 0
if a[i - 1] == b[j - 1]:
return 1 + solve(i - 1, j - 1)
return max(solve(i - 1, j), solve(i, j - 1))
return solve(len(a), len(b))
# ---- way 2: tabulation (bottom-up, 2D) ----
def lcs_tab(a, b):
m, n = len(a), len(b)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 1):
if a[i - 1] == b[j - 1]:
dp[i][j] = dp[i - 1][j - 1] + 1
else:
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
return dp[m][n]
# ---- way 3: O(n) space (two rolling rows) ----
def lcs_fast(a, b):
m, n = len(a), len(b)
prev = [0] * (n + 1)
for i in range(1, m + 1):
cur = [0] * (n + 1)
for j in range(1, n + 1):
if a[i - 1] == b[j - 1]:
cur[j] = prev[j - 1] + 1
else:
cur[j] = max(prev[j], cur[j - 1])
prev = cur
return prev[n]
# ---- tests ----
cases = [
("abcde", "ace", 3),
("abc", "abc", 3),
("abc", "def", 0),
("", "abc", 0),
("abc", "", 0),
("bl", "yby", 1),
("AGGTAB", "GXTXAYB", 4), # "GTAB"
("aaaa", "aa", 2),
]
for a, b, want in cases:
assert lcs_memo(a, b) == want, (a, b, lcs_memo(a, b))
assert lcs_tab(a, b) == want, (a, b, lcs_tab(a, b))
assert lcs_fast(a, b) == want, (a, b, lcs_fast(a, b))
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#16-line-by-line-code-explanation}
- `lcs_memo`: ভেতরের `solve(i, j)` দুই prefix-এর LCS দেয়; `lru_cache` repeated `(i, j)` জোড়া cache করে; শেষ character match হলে diagonal + 1, নয়তো দুই বিকল্পের max।
- `lcs_tab`: `(m+1) x (n+1)` table শূন্যে শুরু (base case এমনিই হয়ে যায়); দুই nested loop প্রতিটা cell-এ transition প্রয়োগ করে; answer `dp[m][n]`।
- `lcs_fast`: পুরো table না রেখে শুধু আগের row (`prev`) আর চলতি row (`cur`); `prev[j-1]` হলো diagonal — তাই rolling-এও ঠিক কাজ করে।
### Output মিলিয়ে দেখা {#17-output-walkthrough}
`cases`-এ আটটা input: classic `"ace"`, identical strings, সম্পূর্ণ disjoint, দুটো খালি-string edge, single-match `"bl"/"yby"`, একটা bioinformatics-ধাঁচের `"AGGTAB"/"GXTXAYB"` (LCS `"GTAB"`), আর repeated-character `"aaaa"/"aa"`। প্রতিটার জন্য তিন function-ই একই উত্তর দিতে হবে। সব pass হলে শেষে print: `সব test pass!`।
### JavaScript ও test cases {#25-javascript-solution-with-test-cases}
Two-prefix 2D DP; match হলে diagonal+1, নয়তো `max(উপর, বাঁ)`। 2D array `Array.from` দিয়ে।
```javascript
const assert = (cond, msg = "") => { if (!cond) throw new Error("FAIL " + msg); };
// dp[i][j] = a-র প্রথম i ও b-র প্রথম j character-এর LCS length
function lcs(a, b) {
const m = a.length, n = b.length;
// (m+1)x(n+1) grid, প্রতিটা row আলাদা array
const dp = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0));
for (let i = 1; i <= m; i++) {
for (let j = 1; j <= n; j++) {
if (a[i - 1] === b[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + 1; // শেষ character match -> diagonal+1
} else {
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]); // যেকোনো একটার শেষ বাদ
}
}
}
return dp[m][n];
}
// ---- test cases (example + edge) ----
const cases = [
["abcde", "ace", 3],
["abc", "abc", 3],
["abc", "def", 0],
["", "abc", 0], // খালি string edge
["abc", "", 0],
["bl", "yby", 1],
["AGGTAB", "GXTXAYB", 4], // "GTAB"
["aaaa", "aa", 2],
];
for (const [a, b, want] of cases) {
assert(lcs(a, b) === want, "lcs " + a + "/" + b);
}
console.log("সব JS test pass!");
```
> **JS টীকা:** `(m+1)x(n+1)` 2D DP grid বানাতে `Array.from({length: m+1}, () => new Array(n+1).fill(0))` — প্রতিটা `() => ...` নতুন row দেয়; `new Array(m+1).fill(new Array(n+1))` সব row এক reference করিয়ে দিত (এক cell লিখলে সব row বদলায়)। index off-by-one: `a[i-1]`/`b[j-1]` (dp[i] মানে প্রথম i character, শেষটা index i-1)।
### TypeScript ও test cases {#26-typescript-solution-with-test-cases}
```typescript
function lcs(a: string, b: string): number {
const m: number = a.length, n: number = b.length;
const dp: number[][] = Array.from({ length: m + 1 }, () => new Array