Longest common subsequence problem is the problem of finding the longest common subsequence that is present in given sequence in same order. i.e. find longest sequence which can be obtained from the first original sequence by deleting some items, and from the second original sequence by deleting other items.

Example:

Given two sequence say “ABACCD” and “ACDF”

Find Longest Common Subsequence or LCS

ABACCD      ACDF
^           ^
SAME (so we mark them and move to next letters)[A]BACCD    [A]CDF
   ^           ^
DIFFERENT (so move to next letter)[A]BACCD    [A]CDF
    ^          ^
DIFFERENT (so move to next letter)[A]BACCD    [A]CDF
     ^         ^
SAME (so we mark them and move to next letters)[A]BA[C]CD  [A][C]DF
        ^         ^
DIFFERENT (so move to next letter)[A]BA[C]CD  [A][C]DF
         ^        ^
SAME (so we mark them)[A]BA[C]C[D]    [A][C][D]F