6
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.
Either your spec is wrong or your sole test case is wrong. This question needs a definition (or at least a reference to a definition) of subsequence, and to be a good question it also needs test cases with better coverage (at a minimum, where S is not a substring of A or B). – Peter Taylor – 2014-02-09T08:46:27.037
@PeterTaylor Why do you think the example is wrong? AB is the longest subsequence which fulfills all three conditions. (It also happends to be a substring of A and B but that doesn't exclude it from the set of solutions.) I agree that the choice of the test case is not sufficient for any case but at least it isn't wrong. – Howard – 2014-02-09T10:04:01.800
My apologies, I misread the test case and got it into my mind that the third parameter was
C
. As @Howard says, it is correct. – Peter Taylor – 2014-02-09T14:51:55.7771Why would case#2 and #4 return 0? Error fallback in case there's no matching sequence? 'SUCKS' isn't a substring of any subsequence, and even if as you say '' is a substring of every string/subsequence, there's nothing saying that '' should be compared...? – Joachim Isaksson – 2014-02-09T15:24:55.767
@JoachimIsaksson My mistake. 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. – Coding man – 2014-02-09T15:55:59.540