LCS — Longest Common Subsequence và thế giới Diff

Mỗi lần bạn chạy git diff, mỗi lần Google Docs highlight thay đổi giữa hai phiên bản, mỗi lần IDE hiện "changes since last save" — đằng sau là thuật toán LCS. Eugene Myers đã dùng LCS làm nền tảng cho diff algorithm trong paper năm 1986, và nó vẫn là core của git diff cho đến hôm nay.

LCS không chỉ là bài toán trên string. Trong bioinformatics, nó so sánh DNA sequences để tìm evolutionary relationship. Trong plagiarism detection, nó phát hiện văn bản sao chép. Trong spell check, edit distance (bài toán anh em) gợi ý từ gần đúng nhất. Hiểu LCS là hiểu nền tảng của mọi bài toán "so sánh hai chuỗi" trong production.

Bài toán: cho hai chuỗi s1 và s2, tìm subsequence chung dài nhất. Subsequence giữ nguyên thứ tự nhưng không cần liên tiếp.

Bức tranh tư duy

Hãy tưởng tượng hai con đường ở Hà Nội: đường Trần Hưng Đạo và đường Hai Bà Trưng. Dù đi theo đường nào, bạn đều đi qua một số giao lộ chung. LCS chính là tìm chuỗi giao lộ chung dài nhất mà bạn đi qua theo đúng thứ tự — bạn không cần qua liên tiếp, nhưng phải theo chiều đi.

Subsequence vs Substring:
  "ABCDE" → Subsequence "ACE" ✓ (giữ thứ tự, không cần liên tiếp)
  "ABCDE" → Substring  "BCD" ✓ (phải liên tiếp)
  "ABCDE" → Subsequence "ECA" ✗ (sai thứ tự)

Ví dụ LCS:
  s1 = "ABCDGH"
  s2 = "AEDFHR"
  LCS = "ADH" (length 3)

       A B C D G H         So sánh từng ký tự:
       ↓     ↓   ↓         A == A → match, thêm A
       A E D F H R         D == D → match, thêm D
                            H == H → match, thêm H

State transition:
  s1[i-1] == s2[j-1] → dp[i][j] = dp[i-1][j-1] + 1   (match → chéo ↖ +1)
  s1[i-1] != s2[j-1] → dp[i][j] = max(dp[i-1][j],     (bỏ s1[i])
                                        dp[i][j-1])     (bỏ s2[j])

Cốt lõi kỹ thuật

Bảng DP 2D — Trực quan hóa

s1 = "AGGTAB",  s2 = "GXTXAYB"

         s2 →
         ""  G   X   T   X   A   Y   B
       ┌─────────────────────────────────┐
    "" │ 0   0   0   0   0   0   0   0   │
     A │ 0   0   0   0   0   1   1   1   │
  s1 G │ 0   1   1   1   1   1   1   1   │
   ↓ G │ 0   1   1   1   1   1   1   1   │
     T │ 0   1   1   2   2   2   2   2   │
     A │ 0   1   1   2   2   3   3   3   │
     B │ 0   1   1   2   2   3   3   4   │
       └─────────────────────────────────┘
                                      ↑
                                LCS = 4 → "GTAB"

Bottom-Up Tabulation — O(M×N) time, O(M×N) space

C++PythonJavaGo

cpp

int lcs(const string& s1, const string& s2) {
    int m = s1.size(), n = s2.size();
    vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));

    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (s1[i-1] == s2[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];
}

python

def lcs(s1: str, s2: str) -> int:
    m, n = len(s1), len(s2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if s1[i-1] == s2[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]

java

public int lcs(String s1, String s2) {
    int m = s1.length(), n = s2.length();
    int[][] dp = new int[m + 1][n + 1];

    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (s1.charAt(i-1) == s2.charAt(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];
}

func lcs(s1, s2 string) int {
    m, n := len(s1), len(s2)
    dp := make([][]int, m+1)
    for i := range dp {
        dp[i] = make([]int, n+1)
    }

    for i := 1; i <= m; i++ {
        for j := 1; j <= n; j++ {
            if s1[i-1] == s2[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]
}

Traceback — Tìm chuỗi LCS thực tế

C++PythonJavaGo

cpp

pair<int, string> lcsWithString(const string& s1, const string& s2) {
    int m = s1.size(), n = s2.size();
    vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));

    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= n; j++)
            dp[i][j] = (s1[i-1] == s2[j-1])
                ? dp[i-1][j-1] + 1
                : max(dp[i-1][j], dp[i][j-1]);

    string result;
    int i = m, j = n;
    while (i > 0 && j > 0) {
        if (s1[i-1] == s2[j-1]) {
            result += s1[i-1];
            i--; j--;
        } else if (dp[i-1][j] > dp[i][j-1]) {
            i--;
        } else {
            j--;
        }
    }
    reverse(result.begin(), result.end());
    return {dp[m][n], result};
}

python

def lcs_with_string(s1: str, s2: str) -> tuple[int, str]:
    m, n = len(s1), len(s2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if s1[i-1] == s2[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])

    # Traceback
    result = []
    i, j = m, n
    while i > 0 and j > 0:
        if s1[i-1] == s2[j-1]:
            result.append(s1[i-1])
            i -= 1; j -= 1
        elif dp[i-1][j] > dp[i][j-1]:
            i -= 1
        else:
            j -= 1
    return dp[m][n], ''.join(reversed(result))

java

public String[] lcsWithString(String s1, String s2) {
    int m = s1.length(), n = s2.length();
    int[][] dp = new int[m + 1][n + 1];

    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= n; j++)
            dp[i][j] = (s1.charAt(i-1) == s2.charAt(j-1))
                ? dp[i-1][j-1] + 1
                : Math.max(dp[i-1][j], dp[i][j-1]);

    StringBuilder sb = new StringBuilder();
    int i = m, j = n;
    while (i > 0 && j > 0) {
        if (s1.charAt(i-1) == s2.charAt(j-1)) {
            sb.append(s1.charAt(i-1));
            i--; j--;
        } else if (dp[i-1][j] > dp[i][j-1]) {
            i--;
        } else {
            j--;
        }
    }
    return new String[]{String.valueOf(dp[m][n]), sb.reverse().toString()};
}

func lcsWithString(s1, s2 string) (int, string) {
    m, n := len(s1), len(s2)
    dp := make([][]int, m+1)
    for i := range dp {
        dp[i] = make([]int, n+1)
    }

    for i := 1; i <= m; i++ {
        for j := 1; j <= n; j++ {
            if s1[i-1] == s2[j-1] {
                dp[i][j] = dp[i-1][j-1] + 1
            } else {
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
            }
        }
    }

    var result []byte
    i, j := m, n
    for i > 0 && j > 0 {
        if s1[i-1] == s2[j-1] {
            result = append(result, s1[i-1])
            i--; j--
        } else if dp[i-1][j] > dp[i][j-1] {
            i--
        } else {
            j--
        }
    }
    // Reverse
    for l, r := 0, len(result)-1; l < r; l, r = l+1, r-1 {
        result[l], result[r] = result[r], result[l]
    }
    return dp[m][n], string(result)
}

Space-Optimized — O(M×N) time, O(min(M,N)) space

Khi chỉ cần độ dài LCS (không cần traceback), chỉ dùng 2 hàng rolling array.

C++PythonJavaGo

cpp

int lcsOptimized(const string& s1, const string& s2) {
    // Đảm bảo s2 ngắn hơn
    const string& a = (s1.size() >= s2.size()) ? s1 : s2;
    const string& b = (s1.size() >= s2.size()) ? s2 : s1;
    int m = a.size(), n = b.size();

    vector<int> prev(n + 1, 0), curr(n + 1, 0);
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            curr[j] = (a[i-1] == b[j-1])
                ? prev[j-1] + 1
                : max(prev[j], curr[j-1]);
        }
        swap(prev, curr);
        fill(curr.begin(), curr.end(), 0);
    }
    return prev[n];
}

python

def lcs_optimized(s1: str, s2: str) -> int:
    if len(s1) < len(s2):
        s1, s2 = s2, s1
    m, n = len(s1), len(s2)

    prev = [0] * (n + 1)
    curr = [0] * (n + 1)
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if s1[i-1] == s2[j-1]:
                curr[j] = prev[j-1] + 1
            else:
                curr[j] = max(prev[j], curr[j-1])
        prev, curr = curr, [0] * (n + 1)
    return prev[n]

java

public int lcsOptimized(String s1, String s2) {
    if (s1.length() < s2.length()) {
        String tmp = s1; s1 = s2; s2 = tmp;
    }
    int m = s1.length(), n = s2.length();

    int[] prev = new int[n + 1], curr = new int[n + 1];
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            curr[j] = (s1.charAt(i-1) == s2.charAt(j-1))
                ? prev[j-1] + 1
                : Math.max(prev[j], curr[j-1]);
        }
        int[] tmp = prev; prev = curr; curr = tmp;
        Arrays.fill(curr, 0);
    }
    return prev[n];
}

func lcsOptimized(s1, s2 string) int {
    if len(s1) < len(s2) {
        s1, s2 = s2, s1
    }
    m, n := len(s1), len(s2)

    prev := make([]int, n+1)
    curr := make([]int, n+1)
    for i := 1; i <= m; i++ {
        for j := 1; j <= n; j++ {
            if s1[i-1] == s2[j-1] {
                curr[j] = prev[j-1] + 1
            } else {
                curr[j] = max(prev[j], curr[j-1])
            }
        }
        prev, curr = curr, make([]int, n+1)
    }
    return prev[n]
}

Edit Distance — Bài toán anh em

Edit Distance (Levenshtein Distance) tính số phép biến đổi tối thiểu (insert, delete, replace) để biến s1 thành s2. Quan hệ: editDistance = len(s1) + len(s2) - 2 * LCS(s1, s2) (khi chỉ cho phép insert/delete).

C++PythonJavaGo

cpp

int editDistance(const string& s1, const string& s2) {
    int m = s1.size(), n = s2.size();
    vector<vector<int>> dp(m + 1, vector<int>(n + 1));

    for (int i = 0; i <= m; i++) dp[i][0] = i;
    for (int j = 0; j <= n; j++) dp[0][j] = j;

    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (s1[i-1] == s2[j-1]) {
                dp[i][j] = dp[i-1][j-1];
            } else {
                dp[i][j] = 1 + min({dp[i-1][j], dp[i][j-1], dp[i-1][j-1]});
            }
        }
    }
    return dp[m][n];
}

python

def edit_distance(s1: str, s2: str) -> int:
    m, n = len(s1), len(s2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    for i in range(m + 1): dp[i][0] = i
    for j in range(n + 1): dp[0][j] = j

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if s1[i-1] == s2[j-1]:
                dp[i][j] = dp[i-1][j-1]
            else:
                dp[i][j] = 1 + min(dp[i-1][j],      # delete
                                    dp[i][j-1],      # insert
                                    dp[i-1][j-1])    # replace
    return dp[m][n]

java

public int editDistance(String s1, String s2) {
    int m = s1.length(), n = s2.length();
    int[][] dp = new int[m + 1][n + 1];

    for (int i = 0; i <= m; i++) dp[i][0] = i;
    for (int j = 0; j <= n; j++) dp[0][j] = j;

    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (s1.charAt(i-1) == s2.charAt(j-1)) {
                dp[i][j] = dp[i-1][j-1];
            } else {
                dp[i][j] = 1 + Math.min(dp[i-1][j],
                    Math.min(dp[i][j-1], dp[i-1][j-1]));
            }
        }
    }
    return dp[m][n];
}

func editDistance(s1, s2 string) int {
    m, n := len(s1), len(s2)
    dp := make([][]int, m+1)
    for i := range dp {
        dp[i] = make([]int, n+1)
        dp[i][0] = i
    }
    for j := 0; j <= n; j++ {
        dp[0][j] = j
    }

    for i := 1; i <= m; i++ {
        for j := 1; j <= n; j++ {
            if s1[i-1] == s2[j-1] {
                dp[i][j] = dp[i-1][j-1]
            } else {
                dp[i][j] = 1 + min(dp[i-1][j], min(dp[i][j-1], dp[i-1][j-1]))
            }
        }
    }
    return dp[m][n]
}

Thực chiến

Tình huống: Simplified Git Diff

Bối cảnh: Xây dựng module so sánh hai phiên bản file — hiển thị dòng thêm (+), xóa (-), giữ nguyên ( ). Đây là phiên bản đơn giản hóa của diff algorithm dùng trong version control.

Mục tiêu: Từ LCS traceback, tạo diff output giống git diff.

python

def compute_diff(old_lines: list[str], new_lines: list[str]) -> list[tuple[str, str]]:
    """
    Simplified diff dùng LCS.
    Returns: list of (operation, line) — operation: ' ', '+', '-'
    """
    m, n = len(old_lines), len(new_lines)
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if old_lines[i-1] == new_lines[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])

    # Traceback tạo diff
    result = []
    i, j = m, n
    while i > 0 or j > 0:
        if i > 0 and j > 0 and old_lines[i-1] == new_lines[j-1]:
            result.append((' ', old_lines[i-1]))
            i -= 1; j -= 1
        elif j > 0 and (i == 0 or dp[i][j-1] >= dp[i-1][j]):
            result.append(('+', new_lines[j-1]))
            j -= 1
        else:
            result.append(('-', old_lines[i-1]))
            i -= 1

    result.reverse()
    return result

# Demo
old = ["def hello():", "    print('Hello')", "    return True"]
new = ["def hello():", "    print('Hello, World!')", "    log('called')", "    return True"]

for op, line in compute_diff(old, new):
    print(f"{op} {line}")
# Output:
#   def hello():
# -     print('Hello')
# +     print('Hello, World!')
# +     log('called')
#       return True

Phân tích:

LCS tìm các dòng giống nhau (keep) → phần còn lại là add/delete
Production diff (Myers algorithm) tối ưu hơn nhưng core vẫn dựa trên LCS
Trade-off: O(M×N) space cho traceback — với file lớn cần streaming approach

Sai lầm điển hình

❌ Sai lầm 1: Nhầm Subsequence với Substring

Vấn đề: Dùng logic "reset khi mismatch" — đó là Longest Common Substring, không phải Subsequence.

python

# SAI: Đây là Longest Common SUBSTRING
if s1[i-1] == s2[j-1]:
    dp[i][j] = dp[i-1][j-1] + 1
else:
    dp[i][j] = 0  # Reset → SAI cho LCS!

Tại sao sai: LCS không yêu cầu liên tiếp. Khi mismatch, ta bỏ 1 ký tự từ s1 hoặc s2, lấy max. Reset về 0 là logic Substring — hoàn toàn khác bài toán.

python

# ĐÚNG: LCS — lấy max khi mismatch
if s1[i-1] == s2[j-1]:
    dp[i][j] = dp[i-1][j-1] + 1
else:
    dp[i][j] = max(dp[i-1][j], dp[i][j-1])  # Không reset!

❌ Sai lầm 2: Traceback sai hướng

Vấn đề: Khi traceback, đi sai hướng khi dp[i-1][j] == dp[i][j-1].

python

# SAI: Không nhất quán khi bằng nhau
while i > 0 and j > 0:
    if s1[i-1] == s2[j-1]:
        result.append(s1[i-1])
        i -= 1; j -= 1
    else:
        i -= 1  # Luôn ưu tiên giảm i → sai khi dp[i][j-1] lớn hơn

Tại sao sai: Khi dp[i-1][j] < dp[i][j-1], phải đi theo hướng j. Nếu luôn giảm i, sẽ bỏ lỡ ký tự LCS nằm ở phía s2.

python

# ĐÚNG: So sánh trước khi chọn hướng
if dp[i-1][j] > dp[i][j-1]:
    i -= 1
else:
    j -= 1

❌ Sai lầm 3: Quên hoán đổi chuỗi ngắn/dài khi tối ưu space

Vấn đề: Luôn dùng s2 làm chiều ngắn mà không kiểm tra.

python

# SAI: Không swap → lãng phí memory
# Nếu s1 = "ab", s2 = "abcdefghij..."
prev = [0] * (len(s2) + 1)  # s2 dài → tốn memory

Tại sao sai: Space optimization dùng O(min(M,N)). Nếu không swap để s2 là chuỗi ngắn hơn, ta dùng O(max(M,N)) — mất ý nghĩa tối ưu.

python

# ĐÚNG: Swap để s2 luôn ngắn hơn
if len(s1) < len(s2):
    s1, s2 = s2, s1
# Bây giờ s2 ngắn hơn → prev, curr có size nhỏ

Under the Hood

Hiệu năng

Approach	Time	Space	Traceback	Ghi chú
Naive Recursion	O(2^(m+n))	O(m+n)	Không	Chỉ giáo dục
Memoization	O(M×N)	O(M×N)	Không trực tiếp	Top-down
2D Tabulation	O(M×N)	O(M×N)	✅ Có	Cần cho diff, LCS string
Space-Optimized	O(M×N)	O(min(M,N))	❌ Không	Chỉ cần length

Họ bài toán LCS

                    LCS
                   / | \
                  /  |  \
    Longest Common  Shortest Common    Edit Distance
    Substring       Supersequence      (Levenshtein)
    (liên tiếp)     (SCS)
        |               |                   |
    DNA Pattern     Merge            Spell Checker
    Matching        Sequences        Autocorrect
                                          |
                                     Diff Algorithm
                                     (git diff)

Bài toán	Khác LCS	Transition
LCS	Subsequence	max(dp[i-1][j], dp[i][j-1])
Longest Common Substring	Liên tiếp	Reset 0 khi mismatch
Edit Distance	Min operations	1 + min(del, ins, rep)
SCS	Chứa cả hai	len(s1) + len(s2) - LCS

LIS ↔ LCS Connection

Longest Increasing Subsequence (LIS) có thể quy về LCS: LIS(arr) = LCS(arr, sorted(arr)). Tuy nhiên, LIS có algorithm O(n log n) với patience sorting, nhanh hơn O(n²) của LCS.

Trade-offs

Yếu tố	2D Full Table	Space-Optimized
Memory	O(M×N) — tốn	O(min(M,N))
Traceback	✅ Diff, LCS string	❌ Chỉ length
Use case	Git diff, DNA alignment	Quick similarity check

Checklist ghi nhớ

✅ Checklist triển khai

Nhận diện bài toán

[ ] Hai chuỗi + "longest/shortest common" → LCS pattern
[ ] "Transform s1 to s2" → Edit Distance
[ ] "Common contiguous" → Substring (khác LCS!)
[ ] "Diff/compare versions" → LCS + traceback

Xây dựng lời giải

[ ] State: dp[i][j] = LCS length của s1[:i] và s2[:j]
[ ] Match: dp[i][j] = dp[i-1][j-1] + 1
[ ] Mismatch: dp[i][j] = max(dp[i-1][j], dp[i][j-1])
[ ] Base: dp[0][j] = dp[i][0] = 0

Traceback

[ ] Match → đi chéo ↖, thêm ký tự vào LCS
[ ] Mismatch → đi theo hướng có giá trị lớn hơn
[ ] Reverse kết quả cuối cùng

Tối ưu hóa

[ ] Space: rolling 2 rows → O(min(M,N))
[ ] Swap s1, s2 nếu cần để s2 ngắn hơn
[ ] Cần traceback → phải giữ full 2D table

Bài toán liên quan

[ ] Edit Distance: thêm operation "replace", base case khác
[ ] Substring: reset 0 khi mismatch
[ ] SCS: LCS + include non-matching characters

Bài tập luyện tập

Bài 1: LCS cơ bản — Foundation

Đề bài: Tìm LCS length và string của s1 = "ABCBDAB", s2 = "BDCAB".

🧠 Quiz

Câu hỏi kiểm tra: LCS length là bao nhiêu?

[ ] A. 3
[x] B. 4
[ ] C. 5
[ ] D. 2 Giải thích: LCS = "BCAB" hoặc "BDAB" (length 4). Có thể có nhiều LCS cùng độ dài. A sai vì bỏ sót match. C sai vì vượt quá length khả thi.

💡 Gợi ý

Vẽ bảng DP 6×5, điền từng ô
Traceback từ dp[5][5] để tìm chuỗi LCS
Có thể có nhiều LCS hợp lệ

✅ Lời giải

python

s1, s2 = "ABCBDAB", "BDCAB"
length, result = lcs_with_string(s1, s2)
print(f"LCS = '{result}' (length {length})")  # "BCAB" (4)

Phân tích: Time O(7×5) = 35 operations. Multiple valid LCS: "BCAB", "BDAB". Traceback path determines which one.

Bài 2: Edit Distance — Intermediate

Đề bài: Tính edit distance giữa "kitten" và "sitting".

🧠 Quiz

Câu hỏi kiểm tra: Edit distance là?

[ ] A. 2
[x] B. 3
[ ] C. 4
[ ] D. 5 Giải thích: kitten → sitten (replace k→s) → sittin (replace e→i) → sitting (insert g). 3 operations. Đây là minimum — không có cách nào ít hơn 3 bước.

✅ Lời giải

python

print(edit_distance("kitten", "sitting"))  # 3

Phân tích: Time O(6×7) = 42 operations. Operations: replace(k,s), replace(e,i), insert(g).

Liên kết học tiếp

Từ khóa glossary: LCS, longest common subsequence, edit distance, Levenshtein, diff algorithm, substring, supersequence, traceback, string DP

Tìm kiếm liên quan: dãy con chung dài nhất, khoảng cách chỉnh sửa, so sánh chuỗi, git diff thuật toán, DP trên chuỗi

LCS — Longest Common Subsequence và thế giới Diff ​

Bức tranh tư duy ​

Cốt lõi kỹ thuật ​

Bảng DP 2D — Trực quan hóa ​

Bottom-Up Tabulation — O(M×N) time, O(M×N) space ​

Traceback — Tìm chuỗi LCS thực tế ​

Space-Optimized — O(M×N) time, O(min(M,N)) space ​

Edit Distance — Bài toán anh em ​

Thực chiến ​

Tình huống: Simplified Git Diff ​

Sai lầm điển hình ​

❌ Sai lầm 1: Nhầm Subsequence với Substring ​

❌ Sai lầm 2: Traceback sai hướng ​

❌ Sai lầm 3: Quên hoán đổi chuỗi ngắn/dài khi tối ưu space ​

Under the Hood ​

Hiệu năng ​

Họ bài toán LCS ​

LIS ↔ LCS Connection ​

Trade-offs ​

Checklist ghi nhớ ​

Bài tập luyện tập ​

Bài 1: LCS cơ bản — Foundation ​

Bài 2: Edit Distance — Intermediate ​

Liên kết học tiếp ​

LCS — Longest Common Subsequence và thế giới Diff

Bức tranh tư duy

Cốt lõi kỹ thuật

Bảng DP 2D — Trực quan hóa

Bottom-Up Tabulation — O(M×N) time, O(M×N) space

Traceback — Tìm chuỗi LCS thực tế

Space-Optimized — O(M×N) time, O(min(M,N)) space

Edit Distance — Bài toán anh em

Thực chiến

Tình huống: Simplified Git Diff

Sai lầm điển hình

❌ Sai lầm 1: Nhầm Subsequence với Substring

❌ Sai lầm 2: Traceback sai hướng

❌ Sai lầm 3: Quên hoán đổi chuỗi ngắn/dài khi tối ưu space

Under the Hood

Hiệu năng

Họ bài toán LCS

LIS ↔ LCS Connection

Trade-offs

Checklist ghi nhớ

Bài tập luyện tập

Bài 1: LCS cơ bản — Foundation

Bài 2: Edit Distance — Intermediate

Liên kết học tiếp