Longest Common Subsequence

Practice this coding question on Coding Gurukul.

Problem statement

Given two strings, find the length of their Longest Common Subsequence (LCS). A subsequence is formed by deleting zero or more characters without changing the order of the remaining characters. Its characters do not have to be adjacent. Print the length only. If the strings have no common character, print 0. Use dynamic programming in O(length of first string * length of second string) time. Worked example ace is a subsequence of abcde and of ace, so the answer is 3.

Input format

Two lines, containing nonempty lowercase strings a and b.

Output format

Print the length of their longest common subsequence.

Constraints

1 <= len(a),len(b) <= 1000; lowercase English letters only.

Sample input

abcde
ace

Sample output

3

Sign in to run or submit a solution in C++, Java or Python.