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.