Interweaving Strings Check | Dataford Interview Questions

Your question is Interweaving Strings Check. 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

An Oscar Health workflow combines two ordered message fragments, such as a member question and a support response. Given strings a, b, and c, determine whether c can be formed by interleaving all characters from a and b while preserving the original left-to-right order within each source string.

Each character in c must come from exactly one of the two input strings. Characters may alternate in any pattern, but characters from the same source cannot be reordered.

Formal Specification

Implement is_interleaving(a, b, c).

Input: three strings a, b, and c.
Output: return True if c is a valid interleaving of a and b; otherwise, return False.
The strings may contain lowercase letters, uppercase letters, digits, spaces, or punctuation. Treat characters as case-sensitive.

Constraints

0 <= len(a), len(b) <= 2,000
0 <= len(c) <= 4,000
Characters are case-sensitive
A valid result requires len(c) == len(a) + len(b)
The target complexity is O(len(a) * len(b)) time

Function Signature

def is_interleaving(a, b, c):