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
- 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.
- Assume the lengths of A, B and C will always be between 1 and 3000 (both inclusive)
One with the shortest code.