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!

  • $\begingroup$ 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. $\endgroup$
    – D.W.
    Dec 11, 2015 at 1:00
  • $\begingroup$ See also cs.stackexchange.com/q/645/755 and cs.stackexchange.com/q/47216/755. $\endgroup$
    – D.W.
    Dec 11, 2015 at 1:01

1 Answer 1


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).

  • $\begingroup$ (How about S = A = "abcde", B = ""?) Can you give a tight upper bound on time complexity? $\endgroup$
    – greybeard
    Dec 11, 2015 at 6:36
  • $\begingroup$ @greybeard I am sorry, I don't get the question ! $\endgroup$
    – mrk
    Dec 11, 2015 at 11:31
  • $\begingroup$ (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? $\endgroup$
    – greybeard
    Dec 11, 2015 at 12:05
  • $\begingroup$ @greybeard The OP asked for a DP solution and there it is. I don't want to prove anything. $\endgroup$
    – mrk
    Dec 11, 2015 at 13:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.