Interleaving String

Asked byAmazonAppleGoogleUberBloomberg

Problem

Given three strings s1, s2, and s3, determine whether s3 can be formed by interleaving s1 and s2 while preserving the relative order of characters from each.

Examples

Example 1

Input:s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"

Output:true

Example 2

Input:s3 = "aadbbbaccc"

Output:false

Constraints

0 <= s1.length, s2.length <= 100
s3.length == s1.length + s2.length

Solve it in the editor. Sign in free to run your Python or JavaScript against test cases, get a verdict, and track your attempts.

Solve on FeatCode →

How to approach it: the 2-D Dynamic Programming pattern

The same DP idea as 1-D, but the state depends on two indices — often two positions in a grid, or a position in each of two sequences being compared.

Look for this pattern when

You're comparing two sequences (finding a longest common subsequence, edit distance).
You're computing paths or optimal values across a 2-D grid.

Read the full 2-D Dynamic Programming guide →

Video walkthroughs

Original problem on LeetCode ↗