Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

Practice › Dynamic Programming

Longest Common Subsequence

Medium · Dynamic Programming · Asked at Amazon, Microsoft, Google

Given two strings a and b, print the length of their longest common subsequence.

A subsequence keeps the order of characters but may skip some.

Input

Two lines: string a and string b (lowercase letters).

Output

Length of the LCS.

Constraints

Example 1

Input

abcde
ace

Output

3

Example 2

Input

abc
def

Output

0

Hints

  1. Let dp[i][j] be the LCS of the first i characters of a and the first j characters of b.
  2. If a[i−1] == b[j−1] then dp[i][j] = dp[i−1][j−1] + 1, otherwise max(dp[i−1][j], dp[i][j−1]).

Approach

Classic 2-D DP over prefixes. When the last characters match, they can end the common subsequence: 1 + dp[i−1][j−1]. When they don't, at least one of them is unused, so take max(dp[i−1][j], dp[i][j−1]). Row 0 and column 0 are 0, since an empty prefix shares nothing. Each row depends only on the previous one, so two rows of memory are enough.

Complexity: O(|a|·|b|) time · O(|b|) space

Solution

C++ solution

#include <bits/stdc++.h>
using namespace std;

int main() {
    string a, b;
    cin >> a >> b;
    int n = a.size(), m = b.size();
    vector<int> prev(m + 1, 0), cur(m + 1, 0);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++)
            cur[j] = (a[i - 1] == b[j - 1]) ? prev[j - 1] + 1 : max(prev[j], cur[j - 1]);
        swap(prev, cur);
    }
    cout << prev[m] << "\n";
    return 0;
}

Python solution

a = input().strip()
b = input().strip()
m = len(b)
prev = [0] * (m + 1)
for ch in a:
    cur = [0] * (m + 1)
    for j in range(1, m + 1):
        if ch == b[j - 1]:
            cur[j] = prev[j - 1] + 1
        else:
            cur[j] = prev[j] if prev[j] > cur[j - 1] else cur[j - 1]
    prev = cur
print(prev[m])

Java solution

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String a = sc.next(), b = sc.next();
        int n = a.length(), m = b.length();
        int[] prev = new int[m + 1], cur = new int[m + 1];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++)
                cur[j] = a.charAt(i - 1) == b.charAt(j - 1) ? prev[j - 1] + 1 : Math.max(prev[j], cur[j - 1]);
            int[] t = prev; prev = cur; cur = t;
        }
        System.out.println(prev[m]);
    }
}

Solve Longest Common Subsequence online · All practice problems