Code Plagiarism

Interview

Time limit1sMemory limit1024 MB

Summary

Given strings s and t, decide whether t can remain after repeatedly deleting any two adjacent characters from s.

Level: Medium5 of 10
Topics: Greedy, Two pointers, String
Solved: No attempts yet

Statement

Alice and Bob are employees of the same well-known company. Each of them proposed a fix for a critical bug to their team lead. Alice suspects that Bob took her code and added characters that do not change its behavior, so that he would look like he worked harder. The company writes code in an esoteric programming language, and each solution is a single line of lowercase Latin letters. Alice's code is the string $t$ , and Bob's code is the string $s$ .

Bob's keyboard is broken, so he can type exactly two characters at a time. The two characters do not have to be the same, and he can insert them at any position in the string. The team lead wants to check whether $t$ can be obtained from $s$ by repeatedly cutting out two adjacent characters. Determine whether $t$ can be obtained from $s$ by cutting out two adjacent characters any number of times.

Input

The first line contains the string $s$ of lowercase Latin letters ( $1 \le |s| \le 2 \cdot 10^5$ ). The second line contains the string $t$ of lowercase Latin letters ( $1 \le |t| \le |s|$ ).

Output

Print YES if $t$ can be obtained from $s$ by cutting out two adjacent characters any number of times. Otherwise, print NO.

Examples3

Example 1
Input
```
sobaka
baka
```
Expected output
```
YES
```
Example 2
Input
```
sobabka
baka
```
Expected output
```
NO
```
Example 3
Input
```
abacaba
aca
```
Expected output
```
YES
```