Interleaving String

First reject when len(s1)+len(s2) != len(s3). Define dp[i][j] as whether the first i characters of s1 and first j of s2 can form the first i+j characters of s3 while preserving each source order. The base dp[0][0] is true. A state is true if the last target character matches s1[i-1] and dp[i-1][j], or matches s2[j-1] and dp[i][j-1]. Fill the first row and column from their single-source matches. This recurrence is exhaustive because the final character of any interleaving prefix must come from exactly one source. Test empty strings, repeated equal characters where both transitions may work, a late mismatch, and equal total length that still cannot interleave. A full table costs O(mn) time and space; update a one-dimensional array left-to-right to use O(min(m,n)) space, being careful that the old and new entries represent different predecessors.