Min Deletions :
Difficulty Level : Medium
Submissions : 438
Asked In :
Marks :100
: 4 | : 0
Given a string with only characters X and Y. Find the minimum number of characters to remove from the string such that there is no interleaving of characters X and Y and all the Xs appear before any Y.
Input
The first and online line of input contains a string S ($$$1 le S \le 1e5$$$)
Output
For each test case print, the minimum number of characters to remove
Examples
Input
YXXXYXY
Output
2
Input
YYXYXX
Output
3
Note
For the first test case :
We can obtain XXXYY by:
Delete the first Y—XXXYXY
Delete the last occurrence of X –XXXYY
