Decide whether S can be interleaved character by character from a subsequence of S and a subsequence of T, both of the same length as S.
Medium6Dynamic programmingStringInterviewNo attempts yetTime limit5sMemory limit512 MBThe head of company S is preparing an M&A with company T. M&A is short for "Mergers and Acquisitions". He claims in public that the two company names get mixed into a new one, but what he actually wants is to keep the original name S after the merger.
By his rule, the name after the M&A is built as follows.
Let s be a subsequence of S and let t be a subsequence of T. The name after the M&A is a string of length ∣S∣ made by laying out the characters of s and t alternately, that is s0t0s1t1⋯ or t0s0t1s1⋯, where sk is the k-th (0-based) character of the string s. Positions 0, 2, 4, and so on of the result are filled in order by one of the two subsequences, and positions 1, 3, 5, and so on are filled in order by the other. When ∣S∣ is odd, the lengths of the two subsequences differ by 1.
A subsequence is a string obtained by erasing zero or more characters from the original string. For example "abe", "abcde" and "" (the empty string) are all subsequences of "abcde".
You are a programmer at the acquiring company. Write a program that decides whether the original name S can be produced by mixing the two company names.
The input is a single test case on two lines.
The first line contains the name S of the company you work for. The second line contains the name T of the company targeted by the M&A. S and T are non-empty and have the same length, and that length is at most 1,000. Both names consist of lowercase English letters only.
Print Yes on the first line if the original company name S can be produced by mixing the two names. Otherwise print No.