You are given a string consisting of lowercase latin letters '' & '' only. Your task is to minimize the size of the string by applying the following three operations as many times as you wish. At a time, you can apply only one operation.
Choose two adjacent characters ( & are adjacent characters) from String –
For example, "aaab". So, we can do the following operations (chosen characters are underlined) —
aaab aab ab b
We cannot minimize it more by applying any of the operations.
So, you have to find the minimum length string that can be gained after applying the operations.
The first line contains an integer , the number of test cases.
The next lines contain a string , denotes the size of the string. Each string will consist of characters '' and ''.
It is guaranteed that the sum of over all testcases doesn't exceed .
For each test case, print the minimum length string which can be gained after applying the operations.
3 aa aaab bbbb
a b b
For the first test case, aa a .
For the third test case, bbbb bbb bb b .
Login to submit
Lets convert all 'ababab' to 'bbbbbb' as they can be minimized to 'bbb'. Then as a result we will ge...