LabEx
Log In Join For Free

Longest Common Subsequence

AlgorithmAlgorithmBeginner
Practice Now

This tutorial is from open-source community. Access the source code

Introduction

In computer science, the longest common subsequence (LCS) problem is to find the longest subsequence common to all sequences in a set of sequences (often just two sequences). It differs from problems of finding common substrings: unlike substrings, subsequences are not required to occupy consecutive positions within the original sequences.

Skills Graph

%%%%{init: {'theme':'neutral'}}%%%% flowchart RL python(("`Python`")) -.-> python/BasicConceptsGroup(["`Basic Concepts`"]) algorithm(("`Algorithm`")) -.-> algorithm/BasicAlgorithmsGroup(["`Basic Algorithms`"]) python(("`Python`")) -.-> python/ControlFlowGroup(["`Control Flow`"]) python(("`Python`")) -.-> python/DataStructuresGroup(["`Data Structures`"]) python(("`Python`")) -.-> python/FunctionsGroup(["`Functions`"]) python(("`Python`")) -.-> python/ModulesandPackagesGroup(["`Modules and Packages`"]) python(("`Python`")) -.-> python/ObjectOrientedProgrammingGroup(["`Object-Oriented Programming`"]) python(("`Python`")) -.-> python/ErrorandExceptionHandlingGroup(["`Error and Exception Handling`"]) python/BasicConceptsGroup -.-> python/comments("`Comments`") algorithm/BasicAlgorithmsGroup -.-> algorithm/arrays_strings("`Arrays Strings`") python/BasicConceptsGroup -.-> python/variables_data_types("`Variables and Data Types`") python/BasicConceptsGroup -.-> python/strings("`Strings`") python/ControlFlowGroup -.-> python/conditional_statements("`Conditional Statements`") python/ControlFlowGroup -.-> python/for_loops("`For Loops`") python/ControlFlowGroup -.-> python/while_loops("`While Loops`") python/ControlFlowGroup -.-> python/list_comprehensions("`List Comprehensions`") python/DataStructuresGroup -.-> python/lists("`Lists`") python/DataStructuresGroup -.-> python/tuples("`Tuples`") python/FunctionsGroup -.-> python/function_definition("`Function Definition`") python/ModulesandPackagesGroup -.-> python/standard_libraries("`Common Standard Libraries`") python/ObjectOrientedProgrammingGroup -.-> python/classes_objects("`Classes and Objects`") python/ObjectOrientedProgrammingGroup -.-> python/encapsulation("`Encapsulation`") python/ErrorandExceptionHandlingGroup -.-> python/raising_exceptions("`Raising Exceptions`") python/FunctionsGroup -.-> python/build_in_functions("`Build-in Functions`") subgraph Lab Skills python/comments -.-> lab-268862{{"`Longest Common Subsequence`"}} algorithm/arrays_strings -.-> lab-268862{{"`Longest Common Subsequence`"}} python/variables_data_types -.-> lab-268862{{"`Longest Common Subsequence`"}} python/strings -.-> lab-268862{{"`Longest Common Subsequence`"}} python/conditional_statements -.-> lab-268862{{"`Longest Common Subsequence`"}} python/for_loops -.-> lab-268862{{"`Longest Common Subsequence`"}} python/while_loops -.-> lab-268862{{"`Longest Common Subsequence`"}} python/list_comprehensions -.-> lab-268862{{"`Longest Common Subsequence`"}} python/lists -.-> lab-268862{{"`Longest Common Subsequence`"}} python/tuples -.-> lab-268862{{"`Longest Common Subsequence`"}} python/function_definition -.-> lab-268862{{"`Longest Common Subsequence`"}} python/standard_libraries -.-> lab-268862{{"`Longest Common Subsequence`"}} python/classes_objects -.-> lab-268862{{"`Longest Common Subsequence`"}} python/encapsulation -.-> lab-268862{{"`Longest Common Subsequence`"}} python/raising_exceptions -.-> lab-268862{{"`Longest Common Subsequence`"}} python/build_in_functions -.-> lab-268862{{"`Longest Common Subsequence`"}} end

Longest Common Subsequence

Problem

Given two strings, find the longest common subsequence. 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. For example, "ACE" is a subsequence of "ABCDE" but not of "AEDCA".

Requirements

To solve this problem, the following requirements must be met:

  • The inputs may not be valid, so the program should handle invalid inputs.
  • The strings are ASCII.
  • The program should be case sensitive.
  • A subsequence is a non-contiguous block of characters.
  • The program should return a string as a result.
  • The program should assume that it fits memory.

Example Usage

Here are some examples of how the program should behave:

  • If str0 or str1 is None, an exception should be raised.
  • If str0 or str1 equals 0, an empty string should be returned.
  • General case:
str0 = 'ABCDEFGHIJ'
str1 = 'FOOBCDBCDE'

result: 'BCDE'

Summary

In summary, the longest common subsequence problem is a classic problem in computer science that involves finding the longest subsequence common to two strings. The program should handle invalid inputs, be case sensitive, and assume that it fits memory.

Other Algorithm Tutorials you may like

Related Algorithm Courses
Quick Start with Algorithm

Quick Start with Algorithm

AlgorithmPython
Beginner
Implementing Queue Data Structure in C

Implementing Queue Data Structure in C

CAlgorithm
Beginner

We use cookies for a number of reasons, such as keeping the website reliable and secure, to improve your experience on our website and to see how you interact with it. By accepting, you agree to our use of such cookies. Privacy Policy