Algorithm if there is a string including subsequences A and B but not F

Question

I'm looking for an efficient alogrithm for the following problem:

We are given as input three strings A, B and F and we need to tell if there is a String X such that A and B are subsequences of X but F is not. The output of the algorithm should be "Yes" or "No".

A subsequence of a string is any string that can be created by removing some letters from the original string, without changing the order of the remaining letters.

For example if A = "aabab", B = "bbaa" and F = "baba", the algorithm should output "Yes", because "aabbaab" has A and B as a subsequence but not F.

Any ideas?

Answer 1

Now that I have thought a bit more about this problem I found a really simple and efficient solution. ;) This problem was really much easier than I first thought. It can be solved in linear O(|A| + |B|) time without any extra space.

The idea is to iterate through the characters of F and take always the maximal part of A and B to the supersequence so that no longer than the current prefix of F is a subsequence of it. The following c++ code clarifies the idea:

int i = 0, j = 0;
for (int k = 0; k < F.size()-1; k++) {
    while (i < A.size() && A[i] != F[k]) i++;
    while (j < B.size() && B[j] != F[k]) j++;
    i++; j++;
    if (i >= A.size() && j >= B.size()) {
        cout << "YES";
        return 0;
    }
}
cout << "NO";