Copy and Push Back solution codechef
Anton loves creating strings!
Anton now wants to create a stringfollowing some specific rules. They are as follows:
Initially,is empty. Then, Anton can perform two types of operations on :
- Choose a lowercase Latin character (an element of ) and append it to . For example, if currently , Anton can turn it into one of .
- Append a copy of to itself. For example, if currently , Anton can turn it into .
However, Anton doesn’t want to perform operationtwice in a row.
You are given a stringconsisting of the lowercase Latin alphabet. Is it possible for Anton to create using his operations any number of times?
- The first line of input will contain a single integer , denoting the number of test cases.
- Each test case consists of two lines of input.
- The first line of each test case contains a single integer , the length of the string .
- The second line of each test case contains a string of length .
For each test case, output on a new line the answer —
YES if Anton can create using his operations, and
Each character of the output may be printed in either uppercase or lowercase. For example, the strings
YeS will all be treated as identical.
- consists of only lowercase Latin characters
- The sum of across all test cases won’t exceed
Sample Input 1
4 2 ab 3 oof 6 aabaab 5 eevee
Sample Output 1
NO YES YES NO
Test case: Anton can create by starting from the empty string and appending using operation . However, there is no way to create — the only way to do so is to use operation again and append ; but this is not allowed.
Test case: Anton can create from the empty string as follows:
- Use operation to append . The current string is .
- Use operation to append the string to itself. The current string is .
- Use operation to append . The string is now , as required.
Test case: can be created as follows:
- Append to the empty string. The current string is .
- Use operation . The current string is .
- Append with operation . The current string is .
- Use operation . The current string is , and we are done.
Test case: It can be shown that no sequence of operations will allow Anton to create the string .