Check whether a string is an interleaving of two other strings
Filed under Optum (UnitedHealth Group)
Free read 1 of 3Confirm that relative order of characters from s1 and s2 must be preserved in s3.
The question
Given three strings s1, s2, and s3, determine whether s3 is formed by an interleaving of s1 and s2.
Constraints
- 0 <= s1.length, s2.length <= 100
- 0 <= s3.length <= 200
- s1, s2, and s3 consist of lowercase English letters.
Examples
- Input
- s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
- Output
- true
- Why
- s3 is formed by interleaving s1 and s2.
Approach
Confirm that relative order of characters from s1 and s2 must be preserved in s3.
Use recursion to explore all possible choices of taking the next character from s1 or s2. Time complexity: O(2^(N+M)).
Use dynamic programming with a 2D boolean table dp[i][j] representing whether s3[0...i+j-1] is an interleaving of s1[0...i-1] and s2[0...j-1]. Time complexity: O(N * M).
Lengths of s1 + s2 not equal to s3 length; completely disjoint strings.
Solution
O(N * M) time, O(N * M) space
class Solution:
def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
if len(s1) + len(s2) != len(s3): return False
dp = [[False] * (len(s2) + 1) for _ in range(len(s1) + 1)]
dp[0][0] = True
for i in range(len(s1) + 1):
for j in range(len(s2) + 1):
if i > 0 and s1[i-1] == s3[i+j-1]: dp[i][j] |= dp[i-1][j]
if j > 0 and s2[j-1] == s3[i+j-1]: dp[i][j] |= dp[i][j-1]
return dp[len(s1)][len(s2)]
Tips
- What they are testing: Test edge cases where one or both input strings are empty, or when lengths do not match.
- Common mistake: Trying a greedy approach which fails when characters from both s1 and s2 match the current character in s3.
Related Optum (UnitedHealth Group) questions
Collected from public candidate posts and coding forums. Updated Nov 2026.