AlgoMaster Logo

Interleaving String

mediumFrequency8 min readUpdated June 23, 2026

Understanding the Problem

This looks like a string matching problem: check whether we can take characters from s1 and s2 in order to form s3. The complication is the branching. When the next character in s3 matches the next available character in both s1 and s2, we have a choice, and the wrong choice can lead to a dead end even when a valid interleaving exists.

For example, with s1 = "aa", s2 = "ab", and s3 = "aaba", a greedy rule that always takes from s1 first consumes both 'a's from s1, then needs 'b' from s2, and that happens to work. But change s3 to "abaa" and the same rule fails: after taking the first 'a' from s1, s3 needs 'b' next, which only s2 can supply, so the second character has to come from s2. A fixed picking order cannot know that ahead of time, because later characters decide which path stays valid.

This points to a cleaner description of the state. How far we have progressed is fully determined by how many characters we have consumed from s1 and s2. If we have used i characters from s1 and j from s2, we must be at position i + j in s3, since every consumed character occupies one position of s3. The problem becomes finding a path through a 2D grid from (0, 0) to (len(s1), len(s2)).

Key Constraints:

  • 0 <= s1.length, s2.length <= 100 → With m and n both up to 100, an O(m * n) table holds at most ~10,000 cells. That rules out anything exponential and points toward a 2D DP.
  • 0 <= s3.length <= 200 → For an interleaving to exist, s3's length must equal s1.length + s2.length. When it does not, we can return false before doing any work.
  • Lowercase English letters only → Repeated characters are what create the ambiguity. When the same letter is available from both strings, a single forward scan cannot decide which to take.

Approach 1: Recursion with Memoization (Top-Down DP)

Intuition

At each step we are at some index i in s1, some index j in s2, and the matching position in s3 is i + j. The decision is whether the next character of s3 comes from s1 or from s2.

If s1[i] matches s3[i + j], we consume that character from s1 and recurse with (i + 1, j). If s2[j] matches s3[i + j], we recurse with (i, j + 1). If either branch reaches the end, the answer is true.

The pair (i, j) is the entire state. We do not track a separate position in s3 because it is always i + j. Many different orderings of choices can reach the same (i, j), so without memoization the recursion recomputes the same subproblems exponentially. Storing each (i, j) result the first time it is computed caps the work at one evaluation per state.

Algorithm

  1. If the lengths of s1 and s2 do not sum to the length of s3, return false immediately.
  2. Define a recursive function dfs(i, j) that returns whether s3[i+j...] can be formed by interleaving s1[i...] and s2[j...].
  3. Base case: if i == len(s1) and j == len(s2), we have matched all of s3, so return true.
  4. If s1[i] == s3[i + j], recursively check dfs(i + 1, j).
  5. If s2[j] == s3[i + j], recursively check dfs(i, j + 1).
  6. Memoize results for each (i, j) pair to avoid recomputation.

Example Walkthrough

1dfs(0,0): s3[0]='a', s1[0]='a' match, s2[0]='d' no match. Try s1.
0
a
i+j=0
1
a
2
d
3
b
4
b
5
c
6
b
7
c
8
a
9
c
1/6

Code

The same recurrence can be filled iteratively, which removes the recursion stack and the per-call overhead.

Approach 2: Bottom-Up DP (2D Table)

Intuition

Define dp[i][j] to mean: can the first i characters of s1 and the first j characters of s2 interleave to form the first i + j characters of s3? This is the same state as the recursion, indexed by prefix lengths rather than remaining suffixes.

Instead of starting from (0, 0) and recursing forward, we fill the table from the base case outward. The cell dp[i][j] is true if either:

  • dp[i - 1][j] is true AND s1[i - 1] == s3[i + j - 1] (we extend by taking one more character from s1), or
  • dp[i][j - 1] is true AND s2[j - 1] == s3[i + j - 1] (we extend by taking one more character from s2).

Algorithm

  1. If len(s1) + len(s2) != len(s3), return false.
  2. Create a boolean table dp of size (m + 1) x (n + 1).
  3. Set dp[0][0] = true (empty strings interleave to form empty string).
  4. Fill the first row: dp[0][j] is true if all characters of s2[0..j-1] match s3[0..j-1].
  5. Fill the first column: dp[i][0] is true if all characters of s1[0..i-1] match s3[0..i-1].
  6. For each cell dp[i][j], check if we can arrive from the top (using s1) or from the left (using s2).
  7. Return dp[m][n].

Example Walkthrough

1Initialize dp[0][0]=true: empty strings interleave to form an empty string.
0
1
2
3
4
5
0
true
false
false
false
false
false
1
false
false
false
false
false
false
2
false
false
false
false
false
false
3
false
false
false
false
false
false
4
false
false
false
false
false
false
5
false
false
false
false
false
false
1/7

Code

Computing row i only reads row i - 1 and cells already written in row i. Two full rows are enough, and with careful ordering a single row suffices.

Approach 3: Space-Optimized DP (1D Array)

Intuition

dp[i][j] depends on only two cells: dp[i-1][j] directly above and dp[i][j-1] directly to the left. When the recurrence reaches back only one row, the 2D table collapses into a single array.

Keep one array dp of size n + 1 and process each row left to right. When we are about to write dp[j] for row i, the slot still holds row i-1's value, which is exactly the "from above" term dp[i-1][j]. The slot dp[j-1] was already overwritten earlier in this same pass, so it holds row i's value, the "from left" term dp[i][j-1]. Reading both before writing dp[j] gives the same recurrence as the 2D version, and the left-to-right order is what keeps the two terms pointing at the right rows.

Algorithm

  1. If len(s1) + len(s2) != len(s3), return false.
  2. Create a 1D boolean array dp of size n + 1.
  3. Set dp[0] = true.
  4. Fill the first row: for each j, dp[j] = dp[j-1] && s2[j-1] == s3[j-1].
  5. For each row i from 1 to m:
    • Update dp[0] for this row: dp[0] = dp[0] && s1[i-1] == s3[i-1].
    • For each column j from 1 to n: dp[j] = (dp[j] && s1[i-1] == s3[i+j-1]) || (dp[j-1] && s2[j-1] == s3[i+j-1]).
  6. Return dp[n].

Example Walkthrough

1Initialize first row: dp[0]=T, dp[1..5]=F (s2[0]='d'!=s3[0]='a')
0
true
1
false
2
false
3
false
4
false
5
false
1/6

Code