Trusted answers to developer questions

What is the Longest Common Subsequence Problem?

Get the Learn to Code Starter Pack

Break into tech with the logic & computer science skills you’d learn in a bootcamp or university — at a fraction of the cost. Educative's hand-on curriculum is perfect for new learners hoping to launch a career.

The Longest Common Subsequence Problem is one of the most famous problems in Dynamic Programming.

A subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements.

A longest subsequence of string s1 and s2 is the length of the longest subsequence which is common in both the strings.

Let’s look at an example to illustrate the concept: Given two strings as input:

s1= "abdca"
s2= "cbda"
Output: 3
svg viewer

This shows the longest possible subsequence of s1 which is “bda.” This can be derived from sequence s1 by deleting the element ‘a’ without changing the order of the remaining elements, hence, the length of string is 3. One brute force solution is to try all possible subsequences of ‘s1’ and ‘s2’ to find the longest one.

The problem can be dealt with various approaches, the most effective of which makes use of Dynamic Programming.

RELATED TAGS

dynamic programming
Copyright ©2024 Educative, Inc. All rights reserved
Did you find this helpful?