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!