Strings s1 and s2 are interleaved into s3 if s3 can be formed by merging s1 and s2 while keeping the relative order of the characters inside each of s1 and s2. Every character of s1 and every character of s2 must be used exactly once, so a valid interleaving has length exactly len(s1) + len(s2).
Decide whether s3 is a valid interleaving of s1 and s2.
Line 1: the string s1 (possibly empty).
Line 2: the string s2 (possibly empty).
Line 3: the string s3 (possibly empty).
All strings contain only lowercase letters a-z.
Print YES if s3 is a valid interleaving of s1 and s2, otherwise print NO.
Example 1
Input
ab cd acbd
Expected
YES
Explanation
"acbd" takes a, then c, then b, then d: the letters of "ab" stay in order and so do those of "cd", so YES.
Example 2
Input
ab cd abdc
Expected
NO
Explanation
"abdc" would need "cd" to appear as d before c, breaking its order, so NO.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →