Write a Program to check whether a string is a valid shuffle of two strings or not

The problem, simply

You get three strings: s1 of length n, s2 of length m, and result. Is result a valid shuffle of s1 and s2?

Valid means: result uses every letter of s1 and every letter of s2, nothing else, and the letters of s1 appear in their original order, and so do the letters of s2. Letters from the two strings may be mixed in any way. This is also called interleaving.

A story to remember it

Picture it

Examples

Way 1: the simple way

Walk the result letter by letter. Each letter must come from the top of one of the piles. If both tops match, try both.

1. If n + m is not the length of result, return false.
2. Let i and j be how many cards you used from each pile. The next result letter is at i + j.
3. If the top of s1 matches it, try taking it. If the top of s2 matches it, try taking that.
4. When the result is used up, it worked.

class Solution {
    public boolean isValidShuffle(String s1, String s2, String result) {
        if (s1.length() + s2.length() != result.length()) return false;
        return take(s1, s2, result, 0, 0);
    }

    private boolean take(String s1, String s2, String r, int i, int j) {
        int k = i + j;                                   // next letter of the result
        if (k == r.length()) return true;
        if (i < s1.length() && s1.charAt(i) == r.charAt(k)
                && take(s1, s2, r, i + 1, j)) return true;   // card from the left pile
        if (j < s2.length() && s2.charAt(j) == r.charAt(k)
                && take(s1, s2, r, i, j + 1)) return true;   // card from the right pile
        return false;
    }
}

How long it takes: when both piles keep offering the same letter, every step can branch in two, up to O(2^(n + m)). Extra room: the call stack, O(n + m).

Way 2: the clever way

The recursion only ever asks about a pair (i, j), so there are at most (n + 1) * (m + 1) different questions. Fill them in a chart.

1. dp[i][j] is true if the first i letters of s1 and the first j letters of s2 can make the first i + j letters of result.
2. dp[0][0] = true.
3. Box (i, j) is true if the box above is true and the next s1 letter, s1[i - 1], equals result[i + j - 1], or if the box on the left is true and s2[j - 1] equals result[i + j - 1].
4. The answer is dp[n][m].

class Solution {
    public boolean isValidShuffle(String s1, String s2, String result) {
        int n = s1.length(), m = s2.length();
        if (n + m != result.length()) return false;
        boolean[][] dp = new boolean[n + 1][m + 1];
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= m; j++) {
                if (i == 0 && j == 0) { dp[0][0] = true; continue; }
                char want = result.charAt(i + j - 1);       // the newest result letter
                boolean fromS1 = i > 0 && dp[i - 1][j] && s1.charAt(i - 1) == want;  // above
                boolean fromS2 = j > 0 && dp[i][j - 1] && s2.charAt(j - 1) == want;  // left
                dp[i][j] = fromS1 || fromS2;
            }
        }
        return dp[n][m];
    }
}

How long it takes: (n + 1) * (m + 1) boxes, each in constant time, O(n * m). Extra room: the chart, O(n * m). Each row only needs the row above, so one row of m + 1 booleans is enough: O(m).

Watch out for

• Skipping the length check. Without it, a result that is missing letters, or has extra ones, can slip through.
• Counting letters is not enough. abcfed has the right letters but the wrong order.
• Off by one. Box (i, j) checks result.charAt(i + j - 1), the last letter of the first i + j.
• The first row and column. They mean "only one pile used so far", and the same rule handles them if you guard i > 0 and j > 0.

What interviewers ask next

• Use O(m) memory. Keep one boolean row and update it left to right: dp[j] = (dp[j] && s1 matches) || (dp[j - 1] && s2 matches).
• Print one valid way to deal the cards. Store which neighbor made each box true, then walk back from (n, m).
• Count how many ways the result can be made. Store numbers instead of booleans and add the two neighbors.
• Three piles? The chart becomes three dimensional, O(n * m * p).
• If the two strings share no letters at all, the greedy scan is correct and runs in O(n + m).

Remember this

Grown-up words: the shuffle is an interleaving, the chart is a 2D DP table over prefixes of both strings, the repeated (i, j) questions are overlapping subproblems, and the rolling single row is space optimization.