Interleaved String Reconstruction — Problem Statement & Solution Guide

StringsMediumPointer Linkage

TimeO(m·n)

SpaceO(min(m, n))

Quick Answer & Algorithm Key Takeaway

Master coding challenges related to Strings and solve the Interleaved String Reconstruction problem optimally.

TopicStrings

PatternPointer Linkage

TimeO(m·n)

SpaceO(min(m, n))

Problem Description

You are given three strings s1, s2, and result. Determine whether result can be obtained by interleaving s1 and s2 while preserving the relative order of characters within each source string. Each character from s1 and s2 must appear exactly once in result, and the combined length of s1 and s2 must equal the length of result.

Input consists of three lines: the first line contains s1, the second line contains s2, and the third line contains result. All strings are non‑empty and consist of lowercase English letters.

Output a single line containing "YES" if result can be formed by a valid interleaving of s1 and s2, otherwise output "NO".

DSA Pattern Breakdown

"Interleaved String Reconstruction"

medium

WHY DOES IT MATTER?

Interleaving checks appear in parsing, compiler design, and data stream merging where order constraints must be respected. Mastering this pattern demonstrates a candidate's ability to model problems as state‑space traversals and to apply DP for overlapping sub‑problems.

OPTIMIZATION CHALLENGE

The key insight is that the DP transition only depends on the immediate previous row or column, allowing the 2‑D table to be compressed into a 1‑D array, cutting space from O(m·n) to O(min(m, n)) without sacrificing correctness.

REAL-WORLD CONNECTION

Think of two ordered event logs being merged into a single audit trail while preserving the chronological order of each individual system. The audit trail must reflect every event exactly once, mirroring the interleaving constraint.

During an interview, start with the DP recurrence on paper, then immediately discuss space reduction. Interviewers love candidates who can trade space for time and articulate the trade‑off clearly.

COMPLEXITY AT A GLANCE

⏱ Time:O(m·n)

💾 Space:O(min(m, n))

Core Theory — Why This Approach?

The interleaving string problem asks whether a target string can be formed by merging two source strings while preserving the relative order of characters from each source. This is a classic example of a dynamic programming (DP) problem that models a two‑dimensional state space: each state (i, j) represents having consumed i characters from s1 and j characters from s2, and we check if the prefix of length i+j of the result matches this consumption. A naive recursive solution explores all 2^(m+n) possible ways to pick characters, which quickly becomes infeasible for lengths beyond ~20 due to exponential blow‑up. By recognizing overlapping sub‑problems—different recursion paths reaching the same (i, j) pair—we can memoize results or fill a DP table iteratively, reducing the time to O(m·n) where m = |s1| and n = |s2|. Further space optimization leverages the fact that each DP row depends only on the previous row, allowing us to collapse the table to a single 1‑D array of size O(min(m, n)).

Interview Questions on This Problem

Q1How would you modify the DP solution if you also need to reconstruct one valid interleaving sequence, not just a boolean answer?

Maintain a predecessor pointer or a separate boolean matrix indicating whether the current cell was reached from the top (taking a character from s1) or left (taking from s2). After filling the DP table, backtrack from the bottom‑right corner to the origin, building the interleaved string by following the stored directions.

Q2Can the interleaving check be performed in O(m + n) time for any special cases? Provide an example.

If one of the strings is empty, the answer is simply a comparison of the other string with the result, which is O(m + n). Another special case is when all characters in s1 and s2 are distinct; a greedy two‑pointer scan suffices because there is no ambiguity about which source a character belongs to.

Q3Explain how you would adapt the algorithm to handle multiple source strings (k > 2) interleaved into a single result.

The DP state generalizes to a k‑dimensional index vector representing how many characters have been taken from each source. The recurrence checks each dimension for a possible match, leading to O(∏|si|) time, which is exponential in k. Practical solutions use BFS with memoization or A* search, but the problem becomes NP‑hard for arbitrary k.

Examples

Example 1

Input

abc
def
adbcef

Output

YES

Explanation: Take a from s1, d from s2, b from s1, c from s1, e from s2, f from s2. The relative order of characters in s1 (a,b,c) and s2 (d,e,f) is preserved, so the interleaving is valid.

Example 2

Input

abc
def
abcfde

Output

NO

Explanation: The characters from s2 appear as f,d,e in result, which violates the required order d,e,f. Therefore the interleaving is not possible.

Example 3

Input

a
b
ba

Output

YES

Explanation: s1 contributes a, s2 contributes b. The order within each string is trivially preserved, so the result is a valid interleaving.

Constraints

1 <= |s1|, |s2| <= 100000
|result| = |s1| + |s2|
All strings consist only of lowercase English letters

Optimal Approach & Strategy

Use DP to store whether a prefix of result can be formed using prefixes of s1 and s2, filling a table in O(m·n) time. Compress the table to one dimension to achieve O(min(m,n)) space.

Brute Force Approach

Recursively try every possible choice of taking the next character from s1 or s2, leading to exponential time. This explores all 2^(m+n) interleavings.

Code Solutions

Language:

JavaScript Solution

Time: O(m·n)

const fs = require('fs');
const input = fs.readFileSync(0, 'utf8').trim().split(/\s+/);
let idx = 0;
const s1 = input[idx++];
const s2 = input[idx++];
const result = input[idx++];

function interleaveCheck(s1, s2, res) {
    const n = s1.length, m = s2.length;
    if (n + m !== res.length) return 'NO';
    const dp = Array.from({ length: n + 1 }, () => Array(m + 1).fill(false));
    dp[0][0] = true;
    for (let i = 0; i <= n; ++i) {
        for (let j = 0; j <= m; ++j) {
            if (!dp[i][j]) continue;
            if (i < n && s1[i] === res[i + j]) dp[i + 1][j] = true;
            if (j < m && s2[j] === res[i + j]) dp[i][j + 1] = true;
        }
    }
    return dp[n][m] ? 'YES' : 'NO';
}

console.log(interleaveCheck(s1, s2, result));

#include <bits/stdc++.h>
using namespace std;

string interleaveCheck(const string& s1, const string& s2, const string& res) {
    int n = s1.size(), m = s2.size();
    if (n + m != (int)res.size()) return "NO";
    vector<vector<bool>> dp(n + 1, vector<bool>(m + 1, false));
    dp[0][0] = true;
    for (int i = 0; i <= n; ++i) {
        for (int j = 0; j <= m; ++j) {
            if (!dp[i][j]) continue;
            if (i < n && s1[i] == res[i + j]) dp[i + 1][j] = true;
            if (j < m && s2[j] == res[i + j]) dp[i][j + 1] = true;
        }
    }
    return dp[n][m] ? "YES" : "NO";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string s1, s2, result;
    if (!(cin >> s1)) return 0;
    cin >> s2 >> result;
    cout << interleaveCheck(s1, s2, result) << "\n";
    return 0;
}

import java.io.*;

public class Main {
    private static String interleaveCheck(String s1, String s2, String res) {
        int n = s1.length();
        int m = s2.length();
        if (n + m != res.length()) return "NO";
        boolean[][] dp = new boolean[n + 1][m + 1];
        dp[0][0] = true;
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= m; j++) {
                if (!dp[i][j]) continue;
                if (i < n && s1.charAt(i) == res.charAt(i + j)) dp[i + 1][j] = true;
                if (j < m && s2.charAt(j) == res.charAt(i + j)) dp[i][j + 1] = true;
            }
        }
        return dp[n][m] ? "YES" : "NO";
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s1 = br.readLine();
        String s2 = br.readLine();
        String result = br.readLine();
        System.out.println(interleaveCheck(s1, s2, result));
    }
}

import sys

def interleave_check(s1: str, s2: str, res: str) -> str:
    n, m = len(s1), len(s2)
    if n + m != len(res):
        return "NO"
    dp = [[False] * (m + 1) for _ in range(n + 1)]
    dp[0][0] = True
    for i in range(n + 1):
        for j in range(m + 1):
            if not dp[i][j]:
                continue
            if i < n and s1[i] == res[i + j]:
                dp[i + 1][j] = True
            if j < m and s2[j] == res[i + j]:
                dp[i][j + 1] = True
    return "YES" if dp[n][m] else "NO"

def main():
    data = sys.stdin.read().strip().split()
    if not data:
        return
    s1, s2, result = data[0], data[1], data[2]
    print(interleave_check(s1, s2, result))

if __name__ == "__main__":
    main()

const fs = require('fs');
const input = fs.readFileSync(0, 'utf8').trim().split(/\s+/);
let idx = 0;
const s1 = input[idx++];
const s2 = input[idx++];
const result = input[idx++];

function interleaveCheck(s1, s2, res) {
    const n = s1.length, m = s2.length;
    if (n + m !== res.length) return 'NO';
    const dp = Array.from({ length: n + 1 }, () => Array(m + 1).fill(false));
    dp[0][0] = true;
    for (let i = 0; i <= n; ++i) {
        for (let j = 0; j <= m; ++j) {
            if (!dp[i][j]) continue;
            if (i < n && s1[i] === res[i + j]) dp[i + 1][j] = true;
            if (j < m && s2[j] === res[i + j]) dp[i][j + 1] = true;
        }
    }
    return dp[n][m] ? 'YES' : 'NO';
}

console.log(interleaveCheck(s1, s2, result));

Asked in Top Tech Interviews

Paytm

Solve in Interative Editor

Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.