PROBLEM LINKSDIFFICULTYCAKEWALK PREREQUISITESAdHoc PROBLEMGiven two strings, say A and B, find whether A is a subsequence of B, or whether B is a subsequence of A. A subsequence is defined as a string obtained from another string, say S, by deleting one or more characters form S, and not changing the order of the remaining characters. QUICK EXPLANATIONIf the length of A is more than the length of B, then A cannot be a subsequence of B. This is obvious because you cannot delete characters from B and end up with a string that has more characters than it did orginally. Thus, if length of A is larger than length of B we can swap them. Now, it only needs to be checked whether A is a subsequence of B. EXPLANATIONChecking whether A is a subsequence of B can be done greedily. Let us find the first occurence of the first character of A in B. for i = 1 to B.length if B[i] == A[1] break i++ If we find that i is larger than B.length, then of course the very first character of A doesn't exist in B. This would mean that it is impossible for A to be a subsequence of B. On the other hand, we have found that the the first character of A occurs in B at position i, first. Now, we can start looking for the second character of A. But, any occurance of the second character of A that occurs before i in B is irrelevant because we cannot perform any operation that changes the order of characters in A (or B for that matter). Thus, we can resume searching for the second character of A in B, after position i. for j = i+1 to B.length if B[j] == A[2] break j++ Using the same arguments as above, if j is not more than B.length, we have to resume searching for the third character of A in B, after position j. When we have found all the characters of A in B, we can safely end the algorithm as well (with a positive). Otherwise we will run out of characters in B and we must return with a negative. The above algorithm will look like the following pseudo code. j = 1 for i = 1 to A.length while j < B.length if B[j] == A[i] break j++ if j > B.length return false i++ j++ return true The complexity of the algorithm is O(A + B), where S is the length of S. If it is not obvious to you why the algorithm isn't O(A * B) note that we never decrement the value of j. In every iteration of the above algorithm we always increment i as well as j, and probably increment j more so. Thus, the algorithm must terminate in at most O(A) iterations of the outer loop and not more than O(B) iterations of the inner loop. Note how this problem differs from the standard Dynamic Programming problem of finding the largest common subsequence between two strings. We could of course solve this problem by finding the longest commong subsequence between A and B as well, but doing so requires O(A * B) which is too slow for the limits set for length of the strings A and B. SETTER'S SOLUTIONSetter's solution will be updated soon. TESTER'S SOLUTIONCan be found here.
This question is marked "community wiki".
asked 14 May '13, 15:14

Can you provide me a link to learn more about dynamic programming to find largest common sub sequence between 2 strings. answered 11 Dec '14, 17:24

@rukshar check this out: http://www.geeksforgeeks.org/dynamicprogrammingset4longestcommonsubsequence/ answered 01 Jan '15, 12:47

Can anyone help me out with what's wrong in my code ? :) answered 26 Feb '15, 20:26

https://www.codechef.com/viewsolution/13395479 what is wrong with the above code ? answered 27 Apr '17, 20:54

Sorry the solution links are broken. Will be fixing them shortly!