50. Check if a String Is a Valid Shuffle of Two Other Strings

Given strings s1, s2 and s3, print 'Yes' if s3 is an interleaving of s1 and s2 - meaning s3 uses every character of s1 and s2 exactly once, and the relative order of s1's characters and of s2's characters is each preserved within s3. Otherwise print 'No'.

Input: The first line contains string s1. The second line contains string s2. The third line contains string s3, whose length equals |s1| + |s2|. Output: Print 'Yes' if s3 is a valid interleaving of s1 and s2, otherwise print 'No'.

1 <= |s1|, |s2| <= 200, |s3| = |s1| + |s2|

The very first length check (combined length must equal the sum of the two source lengths) is a cheap, fast way to reject obviously-invalid inputs before ever building the DP table.

Check whether a third string could have been formed by interleaving two other strings, keeping each one's own internal character order intact. Brute force: Try every possible way of choosing which combined-string characters come from s1 versus s2 recursively - this branches exponentially without memoization, since the same (i,j) sub-state gets recomputed repeatedly. Optimised: Memoizing the recursive sub-states into a 2D DP table (indexed by how many characters of s1 and s2 have been used so far) ensures each (i,j) combination is computed only once - turning an exponential search into a table with only (|s1|+1) * (|s2|+1) cells to fill.

Apply the identical recursive relation as the brute approach, but memoize the boolean result for each (i, j) pair the first time it's computed, so any later call with the same (i, j) returns instantly from the cache. Since there are only O(n*m) distinct (i, j) pairs, each computed once in O(1) additional work, the exponential recursion becomes polynomial. Time: O(n*m) Space: O(n*m)

Fill the same dp[i][j] table bottom-up in increasing order of i, where dp[i][j] means the first i characters of s1 and first j characters of s2 interleave to form the first i+j characters of s3, using the transition dp[i][j] = (s1[i-1]==s3[i+j-1] and dp[i-1][j]) or (s2[j-1]==s3[i+j-1] and dp[i][j-1]). Because row i of the table only ever depends on row i-1 and the current row's own earlier entries, the table can be collapsed to a single 1D array of length m+1 updated in place as i increases, cutting the memory from quadratic to linear while keeping the same O(n*m) time. Time: O(n*m) Space: O(min(n,m))

Define a recursive function on how many characters of s1 and s2 have been consumed so far (i, j), which succeeds if s3's next character (at position i+j) matches s1[i] and the rest interleaves recursively from (i+1, j), or matches s2[j] and the rest interleaves recursively from (i, j+1); the base case succeeds when both i and j have reached the ends of s1 and s2 with all of s3 consumed. Called with no caching, this revisits the same (i, j) states along exponentially many different recursive paths. Time: O(2^(n+m)) Space: O(n+m) recursion depth

1. First check that the combined string's length equals the sum of the two source strings' lengths - if not, immediately answer No. 2. Build a DP table where dp[i][j] means 'can the first (i+j) characters of the combined string be formed using exactly the first i characters of string 1 and the first j characters of string 2'. 3. dp[i][j] is true if EITHER the last character of the combined string at this point matches the end of string 1 (and dp[i-1][j] was true), OR it matches the end of string 2 (and dp[i][j-1] was true).

Time: O(|s1| * |s2|) - filling the entire DP table, one cell per combination of characters consumed from each source string. Space: O(|s1| * |s2|), for the DP table (though this can be optimized down to O(min(|s1|,|s2|)) using a rolling 1D array, since each row only depends on the row before it).

s3 using the exact right multiset of characters but in an order that breaks the required relative ordering ('No'); the minimum sizes |s1| = |s2| = 1; s1, s2 up to length 200 for O(n*m) DP performance.

This is a great example of recognizing that a problem 'feels' like backtracking at first glance, but has heavy overlapping sub-problems - a strong signal to convert it into DP for efficiency.