← Optum (UnitedHealth Group) questions

Check whether a string is an interleaving of two other strings

Filed under Optum (UnitedHealth Group)

Free read 1 of 3

Confirm 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

  1. Confirm that relative order of characters from s1 and s2 must be preserved in s3.

Solution

O(N * M) time, O(N * M) space

Python
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.