Interleaving String

LeetCode 97: Interleaving String Solution & Explanation

Problem Overview

TL;DR: Use one-dimensional dynamic programming to represent reachable positions in a 2D prefix grid, where each state is reached by taking the next character from either s1 or s2.

The LeetCode 97 Solution determines whether s3 can be formed by interleaving all characters of s1 and s2. Characters selected from each source string must remain in their original left-to-right order.

For example, if i characters have been consumed from s1 and j characters have been consumed from s2, then exactly i + j characters have been consumed from s3. At every step, the next character must match either the next unused character of s1 or the next unused character of s2.

Before performing any dynamic programming, the solution verifies that:

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

If this condition fails, forming s3 is impossible.

This Interleaving String problem is a popular interview question because it tests state modeling, grid-based dynamic programming, and space optimization.

Brute Force Approach for Interleaving String

A direct approach explores every possible way to construct s3.

At each position in s3, there are at most two choices:

1. Take the next character from s1, if it matches.
2. Take the next character from s2, if it matches.

The recursion succeeds when all three strings are fully consumed.

Naive Pseudocode

function canInterleave(i, j):
    k = i + j

    if i == len(s1) and j == len(s2):
        return true

    if k == len(s3):
        return false

    valid = false

    if i < len(s1) and s1[i] == s3[k]:
        valid = valid OR canInterleave(i + 1, j)

    if j < len(s2) and s2[j] == s3[k]:
        valid = valid OR canInterleave(i, j + 1)

    return valid

Complexity

In the worst case, the recursion explores a binary decision tree with depth len(s1) + len(s2).

• Time: O(2^(n + m))
• Space: O(n + m) for the recursion stack

where:

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

The same (i, j) state can be reached through many different interleaving choices. Without memoization or dynamic programming, the algorithm recomputes those states repeatedly.

With lengths up to 100 for both source strings, the exponential number of branches can become too large, causing Time Limit Exceeded. The required optimization is to store whether each prefix state has already been determined.

Algorithm Strategy: Dynamic Programming (DP Patterns)

The algorithm maintains a one-dimensional Boolean array:

dp[j]

At the start of processing row i, dp[j] represents whether the state (i - 1, j) was reachable. While processing the row from left to right:

• The old value of dp[j] represents reaching (i, j) from (i - 1, j) by taking a character from s1.
• The already-updated value of dp[j - 1] represents reaching (i, j) from (i, j - 1) by taking a character from s2.

The algorithm enforces the following boundaries:

• dp[0] can only be reached by consuming characters from s1.
• The first row can only be reached by consuming characters from s2.
• A transition is valid only if the selected source character equals s3[i + j - 1].
• The final answer is dp[m], representing the state where all of s1 and all of s2 have been consumed.

The implementation uses O(m) space, where m is the length of s2.

Execution Flow

1. Check whether the combined lengths of s1 and s2 equal the length of s3.

   • If not, return false.

2. Allocate dp with m + 1 Boolean entries.

3. Set dp[0] = true.

   • This represents the empty prefixes of all three strings.

4. Initialize the first row.

   • Only s2 can be consumed when zero characters have been taken from s1.
   • Each dp[j] remains true only if the preceding state was true and s2[j - 1] matches s3[j - 1].

5. Process each character of s1.

   • First update dp[0], because the first column can only use characters from s1.
   • Then process each j from left to right.

6. For each state (i, j):

   • Check the vertical transition using the previous value of dp[j].
   • Check the horizontal transition using the current value of dp[j - 1].
   • Store the logical OR of these two valid transitions in dp[j].

7. After all rows are processed, return dp[m].

   • This is true exactly when the entire s3 can be formed.

Proof of Correctness

We prove that the dynamic programming algorithm returns true if and only if s3 is a valid interleaving of s1 and s2.

State Invariant

For every i and j, the state represented by dp[j] after processing row i is true exactly when:

s3[0 .. i + j - 1]

can be formed by interleaving:

s1[0 .. i - 1]
s2[0 .. j - 1]

while preserving the order of characters in both source strings.

Base Case

At (0, 0), no characters have been consumed from either source string, and the empty prefix of s3 is valid. Therefore:

dp[0] = true

For the first row, only characters from s2 can be used. The initialization marks dp[j] true exactly when all characters in s2[0 .. j - 1] match the corresponding prefix of s3.

Similarly, updating dp[0] during each row verifies prefixes formed using only s1.

Inductive Step

Assume the invariant holds for all states before (i, j) is computed.

A valid construction of state (i, j) must end in exactly one of two ways:

1. The final character came from s1[i - 1].

   • Then state (i - 1, j) must be valid.
   • The character must match s3[i + j - 1].

2. The final character came from s2[j - 1].

   • Then state (i, j - 1) must be valid.
   • The character must match s3[i + j - 1].

The recurrence checks both possibilities and sets the state to true if either is valid. Therefore, every state is computed correctly.

Final State

The final state (n, m) uses every character from s1 and s2. Since the length check guarantees that their total length equals the length of s3, this state is true exactly when the entire s3 is a valid interleaving.

Therefore, the algorithm is correct.

Pattern Reuse Notes

The following problems share the same pattern/subpattern:

• LeetCode 120: Triangle
• LeetCode 63: Unique Paths II
• LeetCode 64: Minimum Path Sum
• LeetCode 1277: Count Square Submatrices with All Ones

They all model a problem using states arranged in a 2D grid, where each cell depends on neighboring cells from an earlier row, an earlier column, or both. The exact value stored differs:

• Triangle tracks an optimal path value.
• Unique Paths II tracks reachability while respecting blocked cells.
• Minimum Path Sum tracks the minimum accumulated cost.
• Count Square Submatrices with All Ones tracks square sizes ending at each cell.
• Interleaving String tracks whether a prefix state is reachable from two source dimensions.

Reference Implementation

C++ Solution for LeetCode 97

1class Solution {
2public:
3    bool isInterleave(string s1, string s2, string s3) {
4        int n = s1.size();
5        int m = s2.size();
6        if (n + m != static_cast<int>(s3.size())) {
7            return false;
8        }
9
10        vector<bool> dp(m + 1, false);
11        dp[0] = true;
12
13        for (int i = 0; i <= n; ++i) {
14            for (int j = 0; j <= m; ++j) {
15                if (i == 0 && j == 0) {
16                    continue;
17                }
18
19                bool takeS1 = i > 0 && dp[j] && s1[i - 1] == s3[i + j - 1];
20                bool takeS2 = j > 0 && dp[j - 1] && s2[j - 1] == s3[i + j - 1];
21                dp[j] = takeS1 || takeS2;
22            }
23        }
24
25        return dp[m];
26    }
27};

Java Solution for LeetCode 97

1class Solution {
2    public boolean isInterleave(String s1, String s2, String s3) {
3        if (s1.length() + s2.length() != s3.length()) {
4            return false;
5        }
6
7        boolean[] dp = new boolean[s2.length() + 1];
8        dp[0] = true;
9
10        for (int j = 1; j <= s2.length(); j++) {
11            dp[j] = dp[j - 1] && s2.charAt(j - 1) == s3.charAt(j - 1);
12        }
13
14        for (int i = 1; i <= s1.length(); i++) {
15            dp[0] = dp[0] && s1.charAt(i - 1) == s3.charAt(i - 1);
16            for (int j = 1; j <= s2.length(); j++) {
17                boolean fromS1 = dp[j] && s1.charAt(i - 1) == s3.charAt(i + j - 1);
18                boolean fromS2 = dp[j - 1] && s2.charAt(j - 1) == s3.charAt(i + j - 1);
19                dp[j] = fromS1 || fromS2;
20            }
21        }
22
23        return dp[s2.length()];
24    }
25}

Python Solution for LeetCode 97

1class Solution:
2    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
3        if len(s1) + len(s2) != len(s3):
4            return False
5
6        dp = [False] * (len(s2) + 1)
7        dp[0] = True
8
9        for j in range(1, len(s2) + 1):
10            dp[j] = dp[j - 1] and s2[j - 1] == s3[j - 1]
11
12        for i in range(1, len(s1) + 1):
13            dp[0] = dp[0] and s1[i - 1] == s3[i - 1]
14            for j in range(1, len(s2) + 1):
15                from_s1 = dp[j] and s1[i - 1] == s3[i + j - 1]
16                from_s2 = dp[j - 1] and s2[j - 1] == s3[i + j - 1]
17                dp[j] = from_s1 or from_s2
18
19        return dp[len(s2)]