Interleaving String

At each position in s3, it either came from s1 or s2. dp[i][j] asks: using exactly i chars from s1 and j chars from s2, can we form s3[0..i+j-1]? The two transitions correspond to the last character coming from s1 or s2. O(m×n) time and space; O(n) space with rolling array.