Merge Strings While Preserving Order

HardPython00:00

Practice interviewer

In session

5 left

00:00

Your question is Merge Strings While Preserving Order. 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.

You need to log in / sign up to run or submit.

Problem

Given two strings s1 and s2, and a target string s3, determine if s3 can be formed by merging s1 and s2 such that the relative order of characters from s1 and s2 is preserved.

Asked in the Loop Interview Round 1 stage. Solved using recursion and backtracking with memoization after interviewer-provided tips.

Input and Output

Implement is_interleaving(s1, s2, s3), where all inputs are strings. Return True if s3 is a valid interleaving of s1 and s2; otherwise return False.

Constraints

0 <= len(s1), len(s2), len(s3) <= 200
s1, s2, and s3 contain lowercase English letters
The target length must equal len(s1) + len(s2) for a valid result

Function Signature

def is_interleaving(s1, s2, s3):

Your solutionPython 3

You need to log in / sign up to run or submit.

Run your code to see test output