# Check if a string can be split into two subsequences

Given a string S of length N, a string A of length M, a string B of length O such that N >= M + O. Check if the string S can be split into two subsequences X and Y such that A = X and B = Y.

Example: S = "abCDEfgH", A = "abfg", B = "CDEH" => answer is Yes S = "abcDEG", A = "acdG", B = "ED"

I found that this can be solved by dynamic programming but having a tough time finding a recursion. Can someone tell me the recursion and also an intuitive explanation of it? Thanks in advance!

• Hello! We discourage posts that simply state a problem out of context, and expect the community to solve it. Assuming you tried to solve it yourself and got stuck, it may be helpful if you wrote your thoughts and what you could not figure out. You may also want to check out our reference questions and other questions on dynamic-programming, or use the search engine of this site to find similar questions that were already answered. – D.W. Dec 11 '15 at 1:00
• – D.W. Dec 11 '15 at 1:01

We'll use indices (i, j, k) to keep track of how much we've seen of each string (S, A, B).
• If we've seen all of S, then return YES if we've seen all of A and all of B,
• If S[i] == A[j], then recurse on (i+1, j+1, k),
• If S[i] == B[k], then recurse on (i+1, j, k+1).
Implement this as a memoized recursive function. This has time complexity O(S * A * B).
• (Given a String $B$ of length zero, can you check the identity of two Strings $S$ and $A$` in $O(|S|\times|A|\times|B|)$ time?) Can you prove there is no way to check the "splitability" described in, say, $O(|S|+|A|+|B|)$ time? – greybeard Dec 11 '15 at 12:05