LeetCode 97 - Interleaving String

This problem asks us to determine whether a string s3 can be formed by interleaving two other strings, s1 and s2. An interleaving means we combine characters from s1 and s2 while preserving the relative order of characters within each original string.

leetcodemediumstringdynamic-programming

LeetCode Problem 97

Difficulty: 🟡 Medium
Topics: String, Dynamic Programming

Solution

Problem Understanding

This problem asks us to determine whether a string s3 can be formed by interleaving two other strings, s1 and s2.

An interleaving means we combine characters from s1 and s2 while preserving the relative order of characters within each original string. We are allowed to alternate between the two strings in any pattern, but we cannot rearrange characters inside either string.

For example, if:

s1 = "abc"
s2 = "def"

then:

"adbcef"

is valid because the order of "abc" remains intact and the order of "def" also remains intact.

However:

"aedbcf"

is invalid because the relative order of characters from "def" has changed.

The input consists of three strings:

  • s1, the first source string
  • s2, the second source string
  • s3, the target string we want to verify

The expected output is a boolean:

  • true if s3 can be formed by interleaving s1 and s2
  • false otherwise

A critical observation is that every character in s3 must come from either s1 or s2, and all characters from both strings must be used exactly once. This immediately gives us an important validation step:

len(s1) + len(s2) == len(s3)

If the lengths do not add up, interleaving is impossible.

The constraints are relatively small:

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

These constraints suggest that an exponential brute-force search would be too slow in the worst case, but a dynamic programming solution with quadratic complexity is practical.

Several edge cases deserve attention upfront. One important case is when one or both strings are empty. If s1 is empty, then s3 must exactly equal s2, and vice versa. Another tricky scenario happens when characters repeat frequently, such as "aaa" and "aaa". A naive greedy strategy can easily make the wrong choice because multiple valid paths may exist temporarily, but only some lead to a valid final answer. We must also handle cases where the lengths match but the ordering constraints make interleaving impossible.

Approaches

Brute Force Approach

A straightforward idea is to recursively try every possible way to build s3.

At any position in s3, we can either:

  • Take the next character from s1, if it matches
  • Take the next character from s2, if it matches

This naturally creates a branching recursion tree.

Suppose we are at indices (i, j) in s1 and s2. Since we have consumed i + j characters, the next character in s3 is:

k = i + j

If:

s1[i] == s3[k]

we recursively try advancing i.

Similarly, if:

s2[j] == s3[k]

we recursively try advancing j.

The brute-force method is correct because it explores every valid interleaving possibility. If any path successfully consumes all characters, the answer is true.

However, this approach becomes extremely slow because many states repeat. The same (i, j) combination can be reached through different paths, causing exponential recomputation.

For example, repeated characters such as:

s1 = "aaa"
s2 = "aaa"

create many overlapping recursive branches.

Key Insight for an Optimal Solution

The major observation is that the problem has overlapping subproblems.

The state of the problem can be fully described by:

(i, j)

where:

  • i characters have been taken from s1
  • j characters have been taken from s2

Since:

k = i + j

the position in s3 is automatically determined.

If we already know whether state (i, j) can form the remaining suffix of s3, we should not recompute it again.

This naturally leads to dynamic programming.

We define:

dp[i][j]

to mean:

Whether the first i characters of s1 and first j characters of s2 can form the first i + j characters of s3.

Instead of recomputing possibilities repeatedly, we build answers incrementally.

Because each state depends only on the previous row and current row, we can optimize the memory usage to:

O(s2.length)

which satisfies the follow-up requirement.

Approach Time Complexity Space Complexity Notes
Brute Force O(2^(m+n)) O(m+n) Tries every interleaving recursively
Optimal Dynamic Programming O(m × n) O(n) Uses DP with rolling array optimization

Where:

  • m = len(s1)
  • n = len(s2)

Algorithm Walkthrough

We will use a 1D dynamic programming array to achieve optimal space complexity.

  1. First, check whether the lengths match.

If:

len(s1) + len(s2) != len(s3)

then return False immediately because interleaving is impossible. 2. Create a DP array.

Let:

dp[j]

represent whether:

s1[:i] and s2[:j]

can form:

s3[:i+j]

We only need one row because each state depends on:

  • the current row's left value
  • the previous row's same-column value
  1. Initialize the base case.

Start with:

dp[0] = True

because two empty strings form an empty string. 4. Fill the first row.

This corresponds to using only s2.

If characters continue matching:

s2[j-1] == s3[j-1]

then update:

dp[j]
  1. Iterate through s1.

For each character in s1, update:

dp[0]

because this column means using only s1. 6. Update each DP state.

For every (i, j):

We can reach this state in two ways:

From s1:

dp[j] and s1[i-1] == s3[i+j-1]

This means we were already valid in the previous row.

From s2:

dp[j-1] and s2[j-1] == s3[i+j-1]

This means we extend from the left.

Combine them:

dp[j] = from_s1 or from_s2
  1. Return the final answer.

The last cell:

dp[len(s2)]

tells us whether the complete interleaving is possible.

Why it works

The invariant is:

dp[j] always represents whether the prefixes s1[:i] and s2[:j] can form s3[:i+j].

Every valid interleaving must end with either a character from s1 or a character from s2. The DP transition checks both possibilities and preserves correctness inductively. Since every subproblem is solved exactly once, we avoid redundant work while still considering all valid interleavings.

Python Solution

class Solution:
    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
        m, n = len(s1), len(s2)

        if m + n != len(s3):
            return False

        dp = [False] * (n + 1)
        dp[0] = True

        # Initialize first row using only s2
        for j in range(1, n + 1):
            dp[j] = dp[j - 1] and s2[j - 1] == s3[j - 1]

        # Fill DP table
        for i in range(1, m + 1):
            # Update first column using only s1
            dp[0] = dp[0] and s1[i - 1] == s3[i - 1]

            for j in range(1, n + 1):
                target_index = i + j - 1

                from_s1 = (
                    dp[j]
                    and s1[i - 1] == s3[target_index]
                )

                from_s2 = (
                    dp[j - 1]
                    and s2[j - 1] == s3[target_index]
                )

                dp[j] = from_s1 or from_s2

        return dp[n]

The implementation begins with a length check because mismatched total lengths make interleaving impossible.

The dp array stores the current row of the dynamic programming table. Initially, dp[0] = True because empty prefixes match trivially.

The first row is initialized by checking whether s2 alone can build the beginning of s3.

We then iterate through s1, row by row. For each row, dp[0] is updated to represent whether s1 alone forms the corresponding prefix of s3.

For every internal state, we check two possible transitions:

  • extending from s1
  • extending from s2

If either path is valid, the state becomes True.

At the end, dp[n] represents whether all characters from s1 and s2 successfully form s3.

Go Solution

func isInterleave(s1 string, s2 string, s3 string) bool {
	m, n := len(s1), len(s2)

	if m+n != len(s3) {
		return false
	}

	dp := make([]bool, n+1)
	dp[0] = true

	// Initialize first row using only s2
	for j := 1; j <= n; j++ {
		dp[j] = dp[j-1] && s2[j-1] == s3[j-1]
	}

	// Fill DP table
	for i := 1; i <= m; i++ {
		// Update first column using only s1
		dp[0] = dp[0] && s1[i-1] == s3[i-1]

		for j := 1; j <= n; j++ {
			targetIndex := i + j - 1

			fromS1 := dp[j] &&
				s1[i-1] == s3[targetIndex]

			fromS2 := dp[j-1] &&
				s2[j-1] == s3[targetIndex]

			dp[j] = fromS1 || fromS2
		}
	}

	return dp[n]
}

The Go implementation closely mirrors the Python version. Since Go strings are byte-indexable and the input consists only of lowercase English letters, direct indexing is safe and efficient.

Unlike Python, Go requires explicit slice allocation using:

make([]bool, n+1)

No special handling for nil values is needed because empty strings naturally have length zero and the loops behave correctly.

Worked Examples

Example 1

s1 = "aabcc"
s2 = "dbbca"
s3 = "aadbbcbcac"

We track the DP array after each row.

Initial state:

j 0 1 2 3 4 5
dp T F F F F F

After processing "a" from s1:

| dp | T | F | F | F | F | F |

After processing "aa":

| dp | T | T | T | T | T | F |

After processing more characters, valid paths continue surviving.

Final state:

| dp | F | F | T | F | T | T |

Since:

dp[5] = True

the answer is:

true

Example 2

s1 = "aabcc"
s2 = "dbbca"
s3 = "aadbbbaccc"

The DP transitions eventually fail because character ordering cannot be maintained.

Final state:

dp[5] = False

Result:

false

Example 3

s1 = ""
s2 = ""
s3 = ""

Length check:

0 + 0 = 0

Initialize:

dp = [True]

No loops execute.

Final answer:

True

Complexity Analysis

Measure Complexity Explanation
Time O(m × n) Every (i, j) state is computed once
Space O(n) Only one DP row is stored

Where:

m = len(s1)
n = len(s2)

The algorithm processes each combination of prefixes exactly once. Since there are m × n states, the runtime is quadratic. The memory optimization works because each state depends only on the current row and previous row, allowing us to reuse a single array.

Test Cases

solution = Solution()

assert solution.isInterleave(
    "aabcc", "dbbca", "aadbbcbcac"
) is True  # Provided valid example

assert solution.isInterleave(
    "aabcc", "dbbca", "aadbbbaccc"
) is False  # Provided invalid example

assert solution.isInterleave(
    "", "", ""
) is True  # All strings empty

assert solution.isInterleave(
    "", "abc", "abc"
) is True  # Empty s1

assert solution.isInterleave(
    "abc", "", "abc"
) is True  # Empty s2

assert solution.isInterleave(
    "abc", "def", "adbcef"
) is True  # Standard interleaving

assert solution.isInterleave(
    "abc", "def", "abdecf"
) is True  # Different valid ordering

assert solution.isInterleave(
    "abc", "def", "aedbcf"
) is False  # Order violation

assert solution.isInterleave(
    "aaa", "aaa", "aaaaaa"
) is True  # Repeated characters

assert solution.isInterleave(
    "abc", "def", "abcdefg"
) is False  # Length mismatch

assert solution.isInterleave(
    "a", "b", "ba"
) is True  # Starts with s2

assert solution.isInterleave(
    "a", "b", "ab"
) is True  # Starts with s1

assert solution.isInterleave(
    "abc", "xyz", "axbycz"
) is True  # Alternating pattern

assert solution.isInterleave(
    "abc", "xyz", "abxcyz"
) is True  # Mixed grouping
Test Why
("aabcc", "dbbca", "aadbbcbcac") Valid provided example
("aabcc", "dbbca", "aadbbbaccc") Invalid provided example
("", "", "") Empty input boundary
("", "abc", "abc") Empty s1
("abc", "", "abc") Empty s2
("abc", "def", "adbcef") Standard valid interleaving
("abc", "def", "abdecf") Different valid ordering
("abc", "def", "aedbcf") Ordering violation
("aaa", "aaa", "aaaaaa") Repeated characters
("abc", "def", "abcdefg") Length mismatch
("a", "b", "ba") Interleaving beginning with s2
("a", "b", "ab") Interleaving beginning with s1
("abc", "xyz", "axbycz") Alternating merge
("abc", "xyz", "abxcyz") Grouped interleaving

Edge Cases

Empty Strings

One or more input strings may be empty. This case is easy to mishandle if the implementation assumes both source strings contain characters.

For example:

s1 = ""
s2 = "abc"
s3 = "abc"

The implementation handles this naturally because the DP initialization fills the first row using only s2. Similarly, when both strings are empty, dp[0] = True correctly returns True.

Length Mismatch

If:

len(s1) + len(s2) != len(s3)

then interleaving is impossible regardless of character arrangement.

This early exit prevents unnecessary computation and avoids subtle indexing bugs later in the DP transitions.

Example:

s1 = "abc"
s2 = "def"
s3 = "abcdefg"

Since the lengths do not match, the function immediately returns False.

Repeated Characters

Repeated characters can trick greedy solutions.

Example:

s1 = "aaa"
s2 = "aaa"
s3 = "aaaaaa"

At many positions, both s1 and s2 contain matching characters. A greedy algorithm may choose incorrectly and get stuck later.

The dynamic programming solution avoids this issue by exploring both possibilities implicitly and storing valid states, ensuring no correct path is discarded prematurely.

Order Preservation Violations

Characters may all exist in s3, yet the order inside s1 or s2 could be broken.

Example:

s1 = "abc"
s2 = "def"
s3 = "aedbcf"

Although every character appears exactly once, the order of "def" is violated. The DP transition rules prevent invalid sequences because each character must match the correct next character from the corresponding source string.