Find Longest Common Subsequence - Coding Interview Question

In this post, we will solve very popular dynamic programming coding interview questions on Strings.

Problem Statement

Given two strings text1 and text2, return the length of their longest common subsequence. If there is no common subsequence, return 0.

A subsequence of a string is a new string generated from the original string with some characters (can be none) deleted without changing the relative order of the remaining characters.

For example, "ace" is a subsequence of "abcde".

A common subsequence of two strings is a subsequence that is common to both strings.

Solutions

Before trying to solve the problem, let’s be very clear on what subsequence means:

A subsequence of a string is a sequence that can be derived from the original string by deleting some (can be none) characters without changing the order of the remaining characters.

This is not the same as a substring, which requires consecutive characters.

For example, let’s consider the string “ABC”. Here are all possible subsequences of this string:

• “” (the empty string is always a subsequence)
• “A”
• “B”
• “C”