Interleaving Strings Coding | Dataford Interview Questions

Your question is Interleaving Strings Coding. Start with the requirements on the right.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Problem

In a Beyondsoft engineering workflow, two ordered event streams may be merged into one trace. Given strings s1, s2, and s3, determine whether s3 can be formed by interleaving characters from s1 and s2 while preserving the left-to-right order of characters within each source string.

Each character in s3 must come from exactly one source string. Characters from the two sources may be chosen in any order, including consecutive characters from the same source.

Formal Specification

Implement is_interleaving(s1, s2, s3).

Input: Three strings s1, s2, and s3.
Output: Return True if s3 is a valid interleaving of s1 and s2; otherwise return False.
The comparison is case-sensitive, and repeated characters must be handled correctly.

Constraints

0 <= len(s1), len(s2), len(s3) <= 2000
len(s1) + len(s2) must equal len(s3) for a valid interleaving
Inputs are case-sensitive strings
Repeated characters are allowed
An O(len(s1) * len(s2)) solution is expected

Function Signature

def is_interleaving(s1, s2, s3):