Interleaving String: the idea to remember.

The core insight

At state i,j match the next output character from either source when its next character agrees.

Why it works

The number of output characters consumed is always i plus j, so only two source indices are needed.

The mistake to avoid

Check total length first. Repeated characters may require exploring both valid sources.

Commented Java solution

Use java.util.* imports and a surrounding solution class. Tree snippets assume the standard TreeNode definition; linked lists use ListNode and Clone Graph uses a Node with val and neighbors; Copy Random List uses Node with val, next and random. Read the input assumptions above.

// Java reference adapted from neetcode-gh/leetcode (MIT).
// At state i,j match the next output character from either source when its next character agrees.
public boolean isInterleave(String s1, String s2, String s3) {
    if (s1.length() + s2.length() != s3.length()) {
        return false;
    }

    boolean[][] dp = new boolean[s1.length() + 1][s2.length() + 1];
    dp[s1.length()][s2.length()] = true;

    for (int i = dp.length - 1; i >= 0; i--) for (
        int j = dp[0].length - 1;
        j >= 0;
        j--
    ) {
        if (
            i < s1.length() &&
            s1.charAt(i) == s3.charAt(i + j) &&
            dp[i + 1][j]
        ) {
            dp[i][j] = true;
        }
        if (
            j < s2.length() &&
            s2.charAt(j) == s3.charAt(i + j) &&
            dp[i][j + 1]
        ) {
            dp[i][j] = true;
        }
    }

    return dp[0][0];
}

Java reference adapted from neetcode-gh/leetcode · MIT license

Make the next connection