Interleaving String

Medium
319.

Interleaving String

Interleaving String is a medium coding problem on strings and dynamic programming, asked in Amazon, Google, Microsoft and Meta interviews.

Given three strings s1, s2 and s3, return true if s3 is formed by interleaving s1 and s2.

An interleaving splits both strings into blocks and alternates them, preserving the order within each original string.

Example 1

Input
s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
Output
true

Example 2

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

Example 3

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

Constraints

  • 0 <= s1.length, s2.length <= 15
  • s3.length == s1.length + s2.length is required for a true answer.
  • All strings consist of lowercase English letters.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} s1
 * @param {string} s2
 * @param {string} s3
 * @return {boolean}
 */
var isInterleave = function(s1, s2, s3) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Interleaving String — Solution in Python, Java & C++

Interleaving String solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Interleaving String is a medium coding problem on strings and dynamic programming, asked in Amazon, Google, Microsoft and Meta interviews.

Problem statement

Given three strings s1, s2 and s3, return true if s3 is formed by interleaving s1 and s2.

An interleaving splits both strings into blocks and alternates them, preserving the order within each original string.

Example 1

Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
Output: true

Example 2

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

Example 3

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

Constraints

  • 0 <= s1.length, s2.length <= 15
  • s3.length == s1.length + s2.length is required for a true answer.
  • All strings consist of lowercase English letters.

Hints for Interleaving String

  1. Hint 1

    The lengths must add up; otherwise reject immediately.

  2. Hint 2

    Let dp[i][j] mean the first i characters of s1 and the first j of s2 can interleave into the first i + j of s3.

  3. Hint 3

    The next character of s3 must come from one side or the other — that is exactly the two transitions.

How to solve Interleaving String

dp[i][j] says whether the first i characters of s1 and the first j of s2 can interleave into the first i + j of s3; the next character of s3 comes from one side or the other.

Approach

  1. Reject if len(s1) + len(s2) != len(s3).
  2. Set dp[0][0] = true; then dp[i][j] is true if 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].
  3. Return dp[m][n].

Why it works

The last character of any interleaving prefix must be the last used character of s1 or of s2, so the two transitions cover every case and the table is exact.

Complexity

  • Time — O(m · n)
  • Space — O(m · n), reducible to one row

Pitfalls

  • The length check is what makes the indexing safe, and it also prunes most rejections instantly.

Reference solution

Python

def isInterleave(s1: str, s2: str, s3: str) -> bool:
    m, n = len(s1), len(s2)
    if m + n != len(s3):
        return False
    dp = [[False] * (n + 1) for _ in range(m + 1)]
    dp[0][0] = True
    for i in range(m + 1):
        for j in range(n + 1):
            if i > 0 and dp[i - 1][j] and s1[i - 1] == s3[i + j - 1]:
                dp[i][j] = True
            if j > 0 and dp[i][j - 1] and s2[j - 1] == s3[i + j - 1]:
                dp[i][j] = True
    return dp[m][n]

Java

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

C++

bool isInterleave(string s1, string s2, string s3) {
    int m = (int) s1.size(), n = (int) s2.size();
    if (m + n != (int) s3.size()) return false;
    vector<vector<bool>> dp(m + 1, vector<bool>(n + 1, false));
    dp[0][0] = true;
    for (int i = 0; i <= m; i++) {
        for (int j = 0; j <= n; j++) {
            if (i > 0 && dp[i - 1][j] && s1[i - 1] == s3[i + j - 1]) dp[i][j] = true;
            if (j > 0 && dp[i][j - 1] && s2[j - 1] == s3[i + j - 1]) dp[i][j] = true;
        }
    }
    return dp[m][n];
}

JavaScript

var isInterleave = function(s1, s2, s3) {
    const m = s1.length, n = s2.length;
    if (m + n !== s3.length) return false;
    const dp = [];
    for (let i = 0; i <= m; i++) dp.push(new Array(n + 1).fill(false));
    dp[0][0] = true;
    for (let i = 0; i <= m; i++) {
        for (let j = 0; j <= n; j++) {
            if (i > 0 && dp[i - 1][j] && s1[i - 1] === s3[i + j - 1]) dp[i][j] = true;
            if (j > 0 && dp[i][j - 1] && s2[j - 1] === s3[i + j - 1]) dp[i][j] = true;
        }
    }
    return dp[m][n];
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 515 strings problems · the whole catalogue

Learn the technique: Strings · Dynamic Programming