Braided Streams

hard

Two services, A and B, write to the same log file. Each service's own lines stay in order, but the file braids them together however the scheduler pleased that day.

You hold service A's transcript a, service B's transcript b, and the merged file c (one character per log line). Return True if c could be exactly such a braid — every character of a and b used once, each transcript's internal order preserved — else False.

Example 1

in a = "aabcc", b = "dbbca", c = "aadbbcbcac"

out True

Braid as "aa" + "dbbc" + "bc" + "a" + "c".

Example 2

in a = "aabcc", b = "dbbca", c = "aadbbbaccc"

out False

Example 3

in a = "", b = "", c = ""

out True

Two silent services, an empty file.

Constraints

· 0 <= len(a), len(b) <= 50
· 0 <= len(c) <= 100
· lowercase letters only