Interleaving String

MediumDynamic ProgrammingString
Category: 2-D Dynamic Programming
Companies that ask this question:
AmazonGoogleFacebook

Approach

Interleaving String

Problem Statement

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 s and t are divided into n and m substrings respectively, such that:

  • s = s1 + s2 + ... + sn
  • t = t1 + t2 + ... + tm
  • |n - m| <= 1
  • The interleaving is s1 + t1 + s2 + t2 + ... or t1 + s1 + t2 + s2 + ...

Note: a + b is the concatenation of strings a and b.

Examples

Example 1:

Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
Output: true
Explanation: One way to obtain s3 is:
Split s1 into s1 = "aa" + "bc" + "c", and s2 into s2 = "dbbc" + "a".
Interleaving the two splits, we get "aa" + "dbbc" + "bc" + "a" + "c" = "aadbbcbcac"

Example 2:

Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"
Output: false

Example 3:

Input: s1 = "", s2 = "", s3 = ""
Output: true

Approach: 2D Dynamic Programming

Intuition

Think of this as navigating a 2D grid where:

  • Moving right = using a character from s2
  • Moving down = using a character from s1
  • Goal: Reach bottom-right corner while matching s3

Key Insight:

  • dp[i][j] = can first i chars of s1 and first j chars of s2 form first i+j chars of s3?
  • At each position, we can arrive from top (using s1[i-1]) or left (using s2[j-1])

Algorithm

  1. Length check:

    • If s1.length + s2.length != s3.length → return false

  2. Create DP table:

    • Size: (m+1) × (n+1) where m = s1.length, n = s2.length
    • dp[i][j] = can s1[0..i-1] and s2[0..j-1] form s3[0..i+j-1]

  3. Base case:

    • dp[0][0] = true (empty strings)
    • First row: can s2 alone form s3?
    • First column: can s1 alone form s3?

  4. Recurrence:

    dp[i][j] = (s1[i-1] == s3[i+j-1] && dp[i-1][j]) ||
           (s2[j-1] == s3[i+j-1] && dp[i][j-1])

  5. Return dp[m][n]

Why This Works

  • Two paths to each cell:
    • From top: Used s1[i-1], check if it matches s3[i+j-1]
    • From left: Used s2[j-1], check if it matches s3[i+j-1]
  • Character index in s3: Always i+j-1 (combining positions from both strings)
  • Order preservation: Moving right/down maintains relative order

Complexity Analysis

  • Time Complexity: O(m × n) - fill entire DP table
  • Space Complexity: O(m × n) - 2D DP table
    • Can be optimized to O(n) using 1D array

Common Patterns

This problem demonstrates:

  1. 2D String DP: State depends on positions in two strings
  2. Path Finding in Grid: Navigate 2D table with constraints
  3. Multiple Sources: Can reach cell from different directions
  4. Character Matching: Compare against third string at combined index

Related Problems

  • Edit Distance
  • Longest Common Subsequence
  • Distinct Subsequences
  • Regular Expression Matching
  • Scramble String

Tips

  1. Index mapping: s3[i+j-1] corresponds to position when using i chars from s1 and j from s2
  2. Length check first: Early return if lengths don't add up
  3. Space optimization: Can use 1D array by processing row by row
  4. Alternative: BFS/DFS: Can solve with graph search + memoization
  5. Edge cases: Handle empty strings carefully

Solution

java
1class Solution {
2    // Solution 1: 2D Dynamic Programming
3    public boolean isInterleave(String s1, String s2, String s3) {
4        int m = s1.length();
5        int n = s2.length();
6
7        // Check length
8        if (m + n != s3.length()) {
9            return false;
10        }
11
12        // dp[i][j] = can s1[0..i-1] and s2[0..j-1] form s3[0..i+j-1]
13        boolean[][] dp = new boolean[m + 1][n + 1];
14
15        // Base case: empty strings
16        dp[0][0] = true;
17
18        // Fill first column (only using s1)
19        for (int i = 1; i <= m; i++) {
20            dp[i][0] = dp[i - 1][0] && s1.charAt(i - 1) == s3.charAt(i - 1);
21        }
22
23        // Fill first row (only using s2)
24        for (int j = 1; j <= n; j++) {
25            dp[0][j] = dp[0][j - 1] && s2.charAt(j - 1) == s3.charAt(j - 1);
26        }
27
28        // Fill the rest of the table
29        for (int i = 1; i <= m; i++) {
30            for (int j = 1; j <= n; j++) {
31                // Can we form s3[i+j-1]?
32                // Option 1: Use s1[i-1]
33                boolean matchS1 = s1.charAt(i - 1) == s3.charAt(i + j - 1) && dp[i - 1][j];
34                // Option 2: Use s2[j-1]
35                boolean matchS2 = s2.charAt(j - 1) == s3.charAt(i + j - 1) && dp[i][j - 1];
36
37                dp[i][j] = matchS1 || matchS2;
38            }
39        }
40
41        return dp[m][n];
42    }
43
44    // Solution 2: 1D DP (Space Optimized)
45    public boolean isInterleaveOptimized(String s1, String s2, String s3) {
46        int m = s1.length();
47        int n = s2.length();
48
49        if (m + n != s3.length()) {
50            return false;
51        }
52
53        // Only need current and previous row
54        boolean[] dp = new boolean[n + 1];
55        dp[0] = true;
56
57        // Fill first row
58        for (int j = 1; j <= n; j++) {
59            dp[j] = dp[j - 1] && s2.charAt(j - 1) == s3.charAt(j - 1);
60        }
61
62        // Fill rest of table row by row
63        for (int i = 1; i <= m; i++) {
64            // Update first column
65            dp[0] = dp[0] && s1.charAt(i - 1) == s3.charAt(i - 1);
66
67            for (int j = 1; j <= n; j++) {
68                boolean matchS1 = s1.charAt(i - 1) == s3.charAt(i + j - 1) && dp[j];
69                boolean matchS2 = s2.charAt(j - 1) == s3.charAt(i + j - 1) && dp[j - 1];
70                dp[j] = matchS1 || matchS2;
71            }
72        }
73
74        return dp[n];
75    }
76
77    // Solution 3: DFS with Memoization
78    public boolean isInterleaveDFS(String s1, String s2, String s3) {
79        if (s1.length() + s2.length() != s3.length()) {
80            return false;
81        }
82
83        Boolean[][] memo = new Boolean[s1.length() + 1][s2.length() + 1];
84        return dfs(s1, s2, s3, 0, 0, memo);
85    }
86
87    private boolean dfs(String s1, String s2, String s3, int i, int j, Boolean[][] memo) {
88        // If we've matched all of s3
89        if (i + j == s3.length()) {
90            return true;
91        }
92
93        // Check memo
94        if (memo[i][j] != null) {
95            return memo[i][j];
96        }
97
98        boolean result = false;
99
100        // Try matching with s1
101        if (i < s1.length() && s1.charAt(i) == s3.charAt(i + j)) {
102            result = dfs(s1, s2, s3, i + 1, j, memo);
103        }
104
105        // Try matching with s2
106        if (!result && j < s2.length() && s2.charAt(j) == s3.charAt(i + j)) {
107            result = dfs(s1, s2, s3, i, j + 1, memo);
108        }
109
110        memo[i][j] = result;
111        return result;
112    }
113}
114
Loading visualizer...