Interleaved String Reconstruction — Problem Statement & Solution Guide
Problem Description
Given two strings s1 and s2 and a third string result, determine if result is an interleaving of s1 and s2, such that the characters in the first string and second string are used exactly once in the interleaved string and they can appear in any order, but the characters of each string must be in their original order in the interleaved string.
Examples
Input
s1 = 'aab', s2 = 'abb', result = 'aababb'
Output
false
Explanation: Step-by-step: 'aab' and 'abb' cannot be interleaved to form 'aababb' because 'abb' is not a substring of 'aababb' and 'aab' is not a substring of 'aababb' either.
Input
s1 = 'abc', s2 = 'def', result = 'abcdef'
Output
false
Explanation: Step-by-step: 'abc' and 'def' cannot be interleaved to form 'abcdef' because 'def' is not a substring of 'abcdef' and 'abc' is not a substring of 'abcdef' either.
Constraints
- 1 ≤ length(s1), length(s2) ≤ 100
- length(s1) + length(s2) = length(result)
- All characters in the strings are lowercase English letters
Optimal Approach & Strategy
A more efficient approach is to use dynamic programming to build a 2D table where each cell represents whether the substrings up to that point are an interleaving. This approach has a time complexity of O(n*m), where n and m are the lengths of the two input strings.
Brute Force Approach
One naive approach is to generate all permutations of the characters in the two input strings and check if the result string matches any of these permutations. However, this approach has a time complexity of O(n!), making it impractical for large strings.
Asked in Top Tech Interviews
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.