017 — Longest Common Subsequence¶

Source¶

Original source: Classic two-string alignment DP exercise
Platform: LeetCode — https://leetcode.com/problems/longest-common-subsequence/
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-এও ফেরে

1. Problem in simple words¶

দুটো string a আর b দেওয়া। তোমাকে এমন একটা সবচেয়ে লম্বা subsequence খুঁজতে হবে যেটা দুটোতেই আছে। Subsequence মানে: original-এর character-গুলো একই order-এ রেখে কিছু character বাদ দিয়ে যা পাও — পাশাপাশি (contiguous) হওয়া লাগে না। তুমি শুধু length চাও।

a = "abcde"
b = "ace"
সবচেয়ে লম্বা shared subsequence: "ace" -> length 3

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 হয়ে যায়।

6. Real-life analogy¶

ভাবো দুজন মানুষ আলাদা আলাদা গান শুনে একটা করে শব্দ-তালিকা লিখল। তুমি জানতে চাও সবচেয়ে লম্বা কোন শব্দ-ক্রম দুজনের তালিকাতেই একই order-এ পাওয়া যায় (মাঝে অন্য শব্দ থাকলেও চলবে)। প্রতিটা শব্দে দাঁড়িয়ে জিজ্ঞেস করো: "দুজনের এই মুহূর্তের শব্দ কি এক? এক হলে দুজনকেই এক ধাপ এগোও আর গোনায় ১ যোগ করো; না হলে যেকোনো একজনকে এক ধাপ এগিয়ে দেখো কে বেশি দেয়।"

7. Visual explanation¶

a = "abcde", b = "ace"। Row = a-র prefix, column = b-র prefix:

        ""   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 বাদ। উত্তর সবসময় নিচের-ডানের ঘরে।

8. Example input and output¶

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")

9. Brute force thinking¶

প্রথম সরল চিন্তা: শেষ character তুলনা করে recurse করো।

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:

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 নিয়ে কী করব") গুটিয়ে যায়।

14. Step-by-step dry run¶

a = "bl", b = "yby", 2D table (rows = a, cols = b):

dp[0][*] = 0, dp[*][0] = 0 (base padding)
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
i=2 (a[1]='l'): সব column-এ mismatch → প্রতিটায় উপর/বাঁ-এর max বহন হয়: dp[2] = [0,0,1,1]
dp[2][3] = 1 → answer

হাতে মিলিয়ে: একমাত্র common character 'b', তাই LCS length 1. ✔

15. Python solution¶

# ---- 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-এও ঠিক কাজ করে।

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!।

18. Time complexity¶

তিন version-ই O(m·n) — প্রতিটা (i, j) জোড়া একবার করে গোনা হয়। (Naive recursion ছিল exponential।)

19. Space complexity¶

Memoization: O(m·n) — cache + recursion stack।
Tabulation: O(m·n) — পুরো 2D table।
Fast version: O(n) — দুটো row।

20. Common mistakes¶

index off-by-one: a[i-1] লেখা উচিত, a[i] নয় — কারণ dp[i] মানে প্রথম i character, তাই শেষটা index i-1।
mismatch-এ diagonal নেওয়া (dp[i-1][j-1]) — তখন match ছাড়াই length বাড়ে; mismatch-এ শুধু উপর/বাঁ-এর max।
LCS (subsequence) আর longest common substring (contiguous) গুলিয়ে ফেলা — substring-এ mismatch হলে 0-এ reset হয়, এখানে নয়।

21. Which basic problem this inherits from¶

ভিত্তি: two-prefix grid state। ../patterns.md-এর "String DP (two-sequence alignment)" family-তে এই dp[i][j] আকৃতিটা ব্যাখ্যা করা আছে, আর ../state-transition-thinking.md-এর "Problem 7 — Edit Distance" section একই grid-skeleton-এর কথা বলে।

22. Similar harder problems¶

Edit Distance (insert/delete/replace সহ) — https://leetcode.com/problems/edit-distance/ (এই tracker-এর #18)
Shortest Common Supersequence — https://leetcode.com/problems/shortest-common-supersequence/
Regular Expression Matching (একই grid, কঠিন transition) — https://leetcode.com/problems/regular-expression-matching/ (#22)

23. Pattern learned¶

Two-prefix string DP: dp[i][j] = দুই string-এর prefix-এর উত্তর; শেষ দুই character match কি না — তার উপর case-split; হাত যায় diagonal/উপর/বাঁ cell-এ। এই কঙ্কাল LCS, Edit Distance, supersequence, alignment — সবগুলোর ভিত্তি।

24. Final summary¶

ভবিষ্যতের আমাকে: "LCS = two-prefix string DP।" State dp[i][j] = a-র প্রথম i ও b-র প্রথম j character-এর LCS length, transition match হলে diagonal+1 নয়তো max(উপর, বাঁ), base সব 0। মনে রেখো: শেষ character-এ মনোযোগ দিলেই বড় প্রশ্ন ছোট subproblem-এ ভেঙে যায় — এই two-string grid-skeleton অনেক DP-তে ফিরে আসবে।

25. JavaScript solution (with test cases)¶

Two-prefix 2D DP; match হলে diagonal+1, নয়তো max(উপর, বাঁ)। 2D array Array.from দিয়ে।

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)।

26. TypeScript solution (with test cases)¶

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<number>(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;
      } else {
        dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
      }
    }
  }
  return dp[m][n];
}
function expect<T>(actual: T, exp: T, msg = ""): void {
  if (actual !== exp) throw new Error(`FAIL ${msg}: got ${actual}`);
}
const cases: Array<[string, string, number]> = [
  ["abcde", "ace", 3],
  ["abc", "abc", 3],
  ["abc", "def", 0],
  ["", "abc", 0],
  ["bl", "yby", 1],
  ["AGGTAB", "GXTXAYB", 4],
  ["aaaa", "aa", 2],
];
for (const [a, b, want] of cases) expect(lcs(a, b), want, "lcs");
console.log("সব TS test pass!");

TS টীকা: dp: number[][] typing দিয়ে grid যে number-এর 2D array তা locked; new Array<number>(n+1) element-type স্পষ্ট। cases: Array<[string, string, number]> tuple-type দুই string ও expected-length জোড়া নিশ্চিত করে, ভুল arity compile-time-এ ধরা পড়ে।

27. কোথায় কাজে লাগে (real-world use)¶

diff / version control: দুই ফাইলের সাধারণ অংশ বের করে কী যোগ/বাদ হয়েছে দেখানো (git diff-এর ভিত LCS)।
Bioinformatics alignment: দুই DNA/protein sequence-এর সবচেয়ে লম্বা shared subsequence বের করা।
Plagiarism / similarity detection: দুই document-এর common ক্রমিক অংশ মেপে সাদৃশ্য নির্ণয়।
Merge / patch tools: তিন-পক্ষীয় merge-এ common base খুঁজতে LCS-ভিত্তিক alignment।
Autocorrect / fuzzy match: দুই string কতটা মিল তা LCS দিয়ে আঁচ করা (edit-distance-এর জ্ঞাতি)।

মূল pattern: two-prefix dp[i][j]; শেষ দুই character match কিনা তার উপর case-split; এই grid-skeleton LCS, edit-distance, alignment সবের ভিত।

মনে রাখার নিয়ম (legal): সব নিজের ভাষায় লেখা; problem statement copy করা হয়নি; official link শুধু attribution-এর জন্য; "asked by Google/Amazon" দাবি নেই — এটা একটা common interview pattern।