Consecutive Duplicates

Given a string s, consisting of "X" and "Y"s, delete the minimum number of characters such that there’s no consecutive "X" and no consecutive "Y".

Constraints

• n ≤ 100,000 where n is the length of s

https://binarysearch.com/problems/Consecutive-Duplicates

Examples

Example 1

Input

• s = YYYXYXX

Output

• answer = YXYX

Explanation

One solution is to delete the first two “Y”s and the last “X”.

Solution