Determine whether one string can be formed by interleaving two other strings while preserving the order of characters from each string.
Interleaving String
You are given three strings s1, s2, and s3. Determine whether s3 can be formed by interleaving s1 and s2.
An interleaving keeps the relative order of characters from each source string. You may take characters from either s1 or s2 one at a time, but you cannot reorder characters within a string.
Return true if s3 can be built this way, otherwise return false.
Notes
- Every character of
s1ands2must be used exactly once. - At each step, the next character of
s3must match the next unused character from eithers1ors2. - This is a classic feasibility problem that is often solved with dynamic programming.
Input Format
- Three strings:
s1,s2, ands3. s3is the candidate merged string.
Output Format
- Return a boolean value:
trueifs3is an interleaving ofs1ands2falseotherwise
Constraints
s1,s2, ands3contain lowercase or arbitrary ASCII characters depending on the platform variant.- The length of
s3must equallen(s1) + len(s2)for an interleaving to be possible. - Solve efficiently for lengths commonly used in interview-style problems.
Example 1
Input
s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
Output
true
Explanation
One valid merge is a a d b b c b c a c, preserving the order of characters from both s1 and s2.
Example 2
Input
s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"
Output
false
Explanation
The third string cannot be formed while preserving the relative order of characters from both source strings.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.