educative.io

Educative

As it said, the problem is similar to LCS, can we solve it in this way?

  1. Calculate the LC-Sequence, as LCS;
  2. return str1.length() + str2.length() - LCS.length();

Example:

s1: "dynamic"
s2: "programming"
LC-sequence: "ami", length: 3

SCS (return) : 15

Explanation:
S1 and s2 has the longest common sequence ami, with length 3. what we need to do is to add the remaining character to LCS.

We need to add s1.length() - LCS.length() plus s2.length() - LCS.length() number of characters to the LCS. Added up, the SCS would be str1.length() + str2.length() - LCS.length();

2 Likes