Interleaving String - Practice Coding Problems

Interleaving String - Problem

Given strings s1, s2, and s3, determine 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 substrings such that:

s = s1 + s2 + ... + sn
t = t1 + t2 + ... + tm
|n - m| ≤ 1

The interleaving is s1 + t1 + s2 + t2 + s3 + t3 + ... or t1 + s1 + t2 + s2 + t3 + s3 + ...

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

Input & Output

Example 1 — Valid Interleaving

$ Input: s1 = "aab", s2 = "axy", s3 = "aaxaby"

› Output: true

💡 Note: We can form s3 by taking: a(s1) + a(s2) + a(s1) + x(s2) + b(s1) + y(s2) = "aaxaby"

Example 2 — Invalid Interleaving

$ Input: s1 = "aab", s2 = "axy", s3 = "aabcxy"

› Output: false

💡 Note: Character 'c' appears in s3 but not in s1 or s2, so interleaving is impossible

Example 3 — Empty String Cases

$ Input: s1 = "", s2 = "", s3 = ""

› Output: true

💡 Note: Empty strings can form an empty string by interleaving

Constraints

0 ≤ s1.length, s2.length ≤ 100
0 ≤ s3.length ≤ 200
s1, s2, and s3 consist of lowercase English letters

Visualization

Tap to expand

Understanding the Visualization

Input Strings

Two source strings s1, s2 and target string s3

Interleaving Process

Alternate taking characters from s1 and s2 while preserving order

Validation

Check if the interleaved result matches s3 exactly

Key Takeaway

🎯 Key Insight: At each position in s3, we know exactly how many characters we've used from s1 and s2, making DP possible

Asked in

G Google 35 f Facebook 28 a Amazon 22 M Microsoft 18

The key insight is that at each position in s3, we know exactly how many characters we've taken from s1 and s2. The optimal approach uses 2D dynamic programming to build a table tracking valid interleaving positions. Time: O(m×n), Space: O(m×n)

Common Approaches

Approach	Time	Space	Notes
✓ 2D Dynamic Programming	O(m×n)	O(m×n)	Build a 2D table to track valid interleaving positions bottom-up
Memoized Recursion	O(m×n×(m+n))	O(m×n×(m+n))	Use recursion with memoization to cache results of subproblems
Recursive Brute Force	O(2^(m+n))	O(m+n)	Try all possible ways to form s3 by recursively choosing from s1 or s2

2D Dynamic Programming — Algorithm Steps

Step 1: Create DP table dp[m+1][n+1] where dp[i][j] means first i chars of s1 and j chars of s2 form first i+j chars of s3
Step 2: Initialize base case: dp[0][0] = true
Step 3: Fill first row and column for single string cases
Step 4: Fill remaining cells: dp[i][j] = (dp[i-1][j] and s1[i-1]==s3[i+j-1]) or (dp[i][j-1] and s2[j-1]==s3[i+j-1])

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize

Set dp[0][0]=true, fill first row and column

Fill Table

For each cell, check if we can extend from left or top

Result

dp[m][n] contains final answer

Code -

solution.c — C

#include <stdio.h>
#include <string.h>
#include <stdbool.h>
#include <stdlib.h>

bool solution(char* s1, char* s2, char* s3) {
    int m = strlen(s1), n = strlen(s2), l = strlen(s3);
    
    if (m + n != l) {
        return false;
    }
    
    // Allocate 2D DP array
    bool** dp = (bool**)malloc((m + 1) * sizeof(bool*));
    for (int i = 0; i <= m; i++) {
        dp[i] = (bool*)calloc(n + 1, sizeof(bool));
    }
    
    dp[0][0] = true;
    
    // Fill first column (only s1)
    for (int i = 1; i <= m; i++) {
        dp[i][0] = dp[i-1][0] && s1[i-1] == s3[i-1];
    }
    
    // Fill first row (only s2)
    for (int j = 1; j <= n; j++) {
        dp[0][j] = dp[0][j-1] && s2[j-1] == s3[j-1];
    }
    
    // Fill the DP table
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            dp[i][j] = (dp[i-1][j] && s1[i-1] == s3[i+j-1]) ||
                       (dp[i][j-1] && s2[j-1] == s3[i+j-1]);
        }
    }
    
    bool result = dp[m][n];
    
    // Free memory
    for (int i = 0; i <= m; i++) {
        free(dp[i]);
    }
    free(dp);
    
    return result;
}

int main() {
    char s1[1001], s2[1001], s3[1001];
    
    fgets(s1, sizeof(s1), stdin);
    s1[strcspn(s1, "\n")] = 0;
    
    fgets(s2, sizeof(s2), stdin);
    s2[strcspn(s2, "\n")] = 0;
    
    fgets(s3, sizeof(s3), stdin);
    s3[strcspn(s3, "\n")] = 0;
    
    bool result = solution(s1, s2, s3);
    printf(result ? "true\n" : "false\n");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(m×n)

Fill each cell in m×n table exactly once

✓ Linear Growth

Space Complexity

O(m×n)

2D DP table of size (m+1)×(n+1)

⚡ Linearithmic Space

180.0K Views

Medium Frequency

~25 min Avg. Time

2.5K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

2D Dynamic Programming — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler