Interleaving String
Given strings s1, s2, and s3, return true if s3 is formed by an interleaving of s1 and s2.
An interleaving of two strings s1 and s2 is formed by dividing them into substrings and combining those substrings while preserving the original order of characters in both strings.
The characters from s1 and s2 must be used exactly once to form s3.
Example 1
Input
s1 = "aabcc" s2 = "dbbca" s3 = "aadbbcbcac"
Output
true
Explanation
s3 can be formed by interleaving s1 and s2 while preserving the character order of both strings.
One valid way is:
s1: a a b c c
s2: d b b c a
s3: a a d b b c b c a c
Therefore, the answer is true.
Example 2
Input
s1 = "aabcc" s2 = "dbbca" s3 = "aadbbbaccc"
Output
false
Explanation
Although s3 has the correct total length, its characters cannot be formed by interleaving s1 and s2 while preserving the order of characters in both strings.
Therefore, the answer is false.
Constraints
Hints:
Hint 1
First check whether:
s1.length + s2.length == s3.length
If not, s3 cannot be an interleaving.
Hint 2
Let dp[i][j] represent whether the first i characters of s1 and the first j characters of s2 can form the first i + j characters of s3.
Author & Technical Reviewer
Technically reviewed by: ExamAdda Technical Review Team
Technical Reviewers, ExamAdda
Software engineers at ExamAdda who check every article's definitions, complexity claims and code examples before and after publishing.
Published
Aug 24, 2026
Last updated
Aug 24, 2026
Content Verification Methodology
Definitions and complexity claims were checked against authoritative computer-science references. Code examples were compiled and tested with standard, boundary and edge-case inputs.
Expected Output