Course4all
Join us on telegram
Home/dsa/Dynamic Programming/Interleaving String

Interleaving String

Master this topic with zero to advance depth.

Interleaving String

Given strings s1, s2, and s3, find whether s3 is formed by an interleaving of s1 and s2.

An interleaving of two strings s and t is a configuration where they are divided into non-empty substrings such that:

  • s = s1 + s2 + ... + sn
  • t = t1 + t2 + ... + tm
  • The interleaving is s1 + t1 + s2 + t2 + s3 + t3 + ... or t1 + s1 + t2 + s2 + t3 + s3 + ...

Visual Representation

s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac" Characters from s1 (bold), s2 (italic): a a d b b c b c a c (a)(a)(d)(b)(b)(c)(b)(c)(a)(c) s1 s1 s2 s2 s2 s1 s2 s1 s2 s1 Result: True
Medium

Examples

Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
Output: true
Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"
Output: false
Approach 1

Level I: Dynamic Programming (Bottom-Up 2D)

Intuition

We use a 2D table dp[i][j] to represent if s3[0...i+j-1] is formed by interleaving s1[0...i-1] and s2[0...j-1].

Thought Process

  1. dp[i][j] is true if:
    • dp[i-1][j] is true AND s1[i-1] == s3[i+j-1]
    • OR dp[i][j-1] is true AND s2[j-1] == s3[i+j-1]
  2. Base case: dp[0][0] = true.
  3. Base case: dp[i][0] matches only against s1. dp[0][j] matches only against s2.
⏱ O(N * M)💾 O(N * M)

Detailed Dry Run

s1="a", s2="b", s3="ab"

i\j""'b'
""TF (s2[0]!=s3[0])
'a'T (s1[0]==s3[0])T (s1[0]==s3[0] or s2[0]==s3[1])
Result: True
java
public class Main {
    public static boolean isInterleave(String s1, String s2, String s3) {
        if (s1.length() + s2.length() != s3.length()) return false;
        boolean[][] dp = new boolean[s1.length() + 1][s2.length() + 1];
        dp[0][0] = true;

        for (int i = 0; i <= s1.length(); i++) {
            for (int j = 0; j <= s2.length(); j++) {
                if (i > 0) dp[i][j] |= (dp[i - 1][j] && s1.charAt(i - 1) == s3.charAt(i + j - 1));
                if (j > 0) dp[i][j] |= (dp[i][j - 1] && s2.charAt(j - 1) == s3.charAt(i + j - 1));
            }
        }
        return dp[s1.length()][s2.length()];
    }

    public static void main(String[] args) {
        System.out.println(isInterleave("aab", "db", "aadbb")); // true
    }
}
Approach 2

Level II: Memoization (Top-Down 2D)

Intuition

The 2D DP bottom-up approach fills the entire table. Top-down memoization only explores reachable states. Both have the same asymptotic complexity.

Visual

s1="a", s2="b", s3="ab" solve(0,0): s1[0]='a'==s3[0] -> solve(1,0) or s2[0]='b'!=s3[0] -> blocked solve(1,0): s2[0]='b'==s3[1] -> solve(1,1)=True
⏱ O(N * M)💾 O(N * M)

Detailed Dry Run

s1="a", s2="b", s3="ab". solve(0,0): 'a'=='a' -> solve(1,0). solve(1,0): 'b'=='b' -> solve(1,1)=True.

java
import java.util.*;

public class Main {
    static Boolean[][] memo;
    public static boolean solve(String s1, String s2, String s3, int i, int j) {
        if (i==s1.length() && j==s2.length()) return true;
        if (i+j >= s3.length()) return false;
        if (memo[i][j] != null) return memo[i][j];
        boolean res = false;
        if (i<s1.length() && s1.charAt(i)==s3.charAt(i+j)) res = solve(s1,s2,s3,i+1,j);
        if (!res && j<s2.length() && s2.charAt(j)==s3.charAt(i+j)) res = solve(s1,s2,s3,i,j+1);
        return memo[i][j] = res;
    }

    public static boolean isInterleave(String s1, String s2, String s3) {
        if (s1.length()+s2.length()!=s3.length()) return false;
        memo = new Boolean[s1.length()+1][s2.length()+1];
        return solve(s1,s2,s3,0,0);
    }

    public static void main(String[] args) {
        System.out.println(isInterleave("aab","db","aadbb")); // true
    }
}
Approach 3

Level III: Space Optimized (1D)

Intuition

Like most 2D matrix DP problems where dp[i][j] only depends on dp[i-1][j] and dp[i][j-1], we can reduce space to O(M) (where M is length of s2).

Logic Steps

  1. Initialize a dp array of size s2.length + 1.
  2. In the outer loop (s1), dp[j] will represent dp[i][j].
  3. dp[j] is updated as (dp[j] && s1[i-1] == s3[i+j-1]) || (dp[j-1] && s2[i-1] == s3[i+j-1]).
⏱ O(N * M)💾 O(M)

Detailed Dry Run

Same logic, but we only keep one row. The 'up' dependency comes from the array value before modification, and 'left' dependency comes from the array value after modification (current row).

java
public class Main {
    public static boolean isInterleave(String s1, String s2, String s3) {
        if (s1.length() + s2.length() != s3.length()) return false;
        boolean[] dp = new boolean[s2.length() + 1];
        dp[0] = true;
        for (int j = 1; j <= s2.length(); j++) {
            dp[j] = dp[j-1] && s2.charAt(j-1) == s3.charAt(j-1);
        }

        for (int i = 1; i <= s1.length(); i++) {
            dp[0] = dp[0] && s1.charAt(i - 1) == s3.charAt(i - 1);
            for (int j = 1; j <= s2.length(); j++) {
                dp[j] = (dp[j] && s1.charAt(i - 1) == s3.charAt(i + j - 1)) || 
                        (dp[j - 1] && s2.charAt(j - 1) == s3.charAt(i + j - 1));
            }
        }
        return dp[s2.length()];
    }

    public static void main(String[] args) {
        System.out.println(isInterleave("a", "b", "ab")); // true
    }
}
← Previous QuestionPalindrome Partitioning II
Next Question →Minimum Cost to Merge Stones