A subsequence is a sequence that can be derived from another sequence by deleting some elements without changing the order of the remaining elements.
Given three strings A, B and C (note the order) as input, find the length of the longest string S such that:
- Condition 1: S is a subsequence of A
- Condition 2: S is a subsequence of B
- Condition 3: C is a substring of S
.
Testcase #1
Input:
ABCDEF
CDEFAB
B
Output:
2
Testcase #2
Input:
HELLO
WORLD
SUCKS
Output:
0
Testcase #3
Input:
ABCXD
BCDEF
CD
Ouput:
3
Testcase #4
Input:
X
Y
Z
Ouput:
0
Note:
- The empty string is regarded as a subsequence as well as a substring of every string.
- Assume all input strings are in uppercase.
- Return 0 as output if any of the first two conditions (Condition 1 and Condition 2) is not going to be satisfied using Condition 3.
Constraints:
- Assume the lengths of A, B and C will always be between 1 and 3000 (both inclusive)
Winner:
One with the shortest code.
C
. As @Howard says, it is correct. \$\endgroup\$