Longest Common Subsequence
Dynamic ProgrammingMediumCompute the longest common subsequence of two strings and trace the DP backtracking path.
Alt+Shift+C
Configuration Panel
Complexity Indices
Time ComplexityO(N * M)
Auxiliary SpaceO(N * M)
Conceptual Overview
Longest Common Subsequence (LCS) finds the longest subsequence present in both strings in the same relative order, but not necessarily contiguously.
Source: CP-Algorithms reference guide