[Solution] Copy and Push Back solution codechef

Copy and Push Back solution codechef – Anton loves creating strings!

Anton now wants to create a string SS following some specific rules. They are as follows:

Initially, SS is empty. Then, Anton can perform two types of operations on SS:

  1. Choose a lowercase Latin character (an element of {a,b,c,,z}{a,b,c,…,z}) and append it to SS. For example, if currently S=𝚌𝚕𝚊𝚙S=clap, Anton can turn it into one of {𝚌𝚕𝚊𝚙𝚊,𝚌𝚕𝚊𝚙𝚋,,𝚌𝚕𝚊𝚙𝚣}{clapa,clapb,…,clapz}.
  2. Append a copy of SS to itself. For example, if currently S=𝚌𝚕𝚊𝚙S=clap, Anton can turn it into 𝚌𝚕𝚊𝚙𝚌𝚕𝚊𝚙clapclap.

However, Anton doesn’t want to perform operation 11 twice in a row.

You are given a string AA consisting of the lowercase Latin alphabet. Is it possible for Anton to create AA using his operations any number of times?

[Solution] Copy and Push Back solution codechef

  • The first line of input will contain a single integer TT, 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 NN, the length of the string AA.
    • The second line of each test case contains a string AA of length NN.

Output Format

For each test case, output on a new line the answer — YES if Anton can create AA using his operations, and NO otherwise.

Each character of the output may be printed in either uppercase or lowercase. For example, the strings YESyes, and YeS will all be treated as identical.

Constraints

  • 1T1051≤T≤105
  • 1N1061≤N≤106
  • AA consists of only lowercase Latin characters
  • The sum of NN across all test cases won’t exceed 106106

[Solution] Copy and Push Back solution codechef

 

4
2
ab
3
oof
6
aabaab
5
eevee

Sample Output 1 

NO
YES
YES
NO

[Solution] Copy and Push Back solution codechef

Test case 11: Anton can create 𝚊a by starting from the empty string and appending 𝚊a using operation 11. However, there is no way to create 𝚊𝚋ab — the only way to do so is to use operation 11 again and append 𝚋b; but this is not allowed.

Test case 22: Anton can create 𝚘𝚘𝚏oof from the empty string as follows:

  • Use operation 11 to append 𝚘o. The current string is 𝚘o.
  • Use operation 22 to append the string to itself. The current string is 𝚘𝚘oo.
  • Use operation 11 to append 𝚏f. The string is now 𝚘𝚘𝚏oof, as required.

Test case 33: 𝚊𝚊𝚋𝚊𝚊𝚋aabaab can be created as follows:

  • Append 𝚊a to the empty string. The current string is 𝚊a.
  • Use operation 22. The current string is 𝚊𝚊aa.
  • Append 𝚋b with operation 11. The current string is 𝚊𝚊𝚋aab.
  • Use operation 22. The current string is 𝚊𝚊𝚋𝚊𝚊𝚋aabaab, and we are done.

Test case 44: It can be shown that no sequence of operations will allow Anton to create the string 𝚎𝚎𝚟𝚎𝚎eevee.

For Solution

Click Here

Leave a Comment