Header Ads Widget

String Game || codechef solution

 

Problem

Alice and Bob are playing a game. They have a common string  of length . The players also have their individual strings  (belonging to Alice) and  (belonging to Bob) which are empty in the beginning. Game begins with Alice and both players take alternate turns.

In her/his turn, the player picks a single character from string , adds it to the end of their individual string and deletes the picked character from string .

The game continues until string  is empty. Find whether there exists a sequence of moves such that the strings  and  are same at the end of the game.

Input Format

  • The first line of input will contain a single integer , denoting the number of test cases.
  • Each test case consists of multiple lines of input.
    • The first line of each test case contains an integer  — the length of the string.
    • The next line contains the strings  consisting of lowercase english alphabets.

Output Format

For each test case, output on a new line, YES if there exists a sequence of moves such that the strings  and  are same at the end of the game, and NO otherwise.

You may print each character of the string in uppercase or lowercase (for example, the strings YESyEsyes, and yeS will all be treated as identical).

Constraints

  • 1103
  • 1105
  •  consists of lowercase english alphabets
  • The sum of  over all test cases does not exceed 2105.

Sample 1:

Input
Output
4
4
abab
5
cbcba
4
abcd
6
pqprqr
YES
NO
NO
YES

Explanation:

Test case 1: Consider the following sequence of moves:

  • Alice picks the first character of string  and adds it to the end of string . Thus,  becomes bab and  becomes a.
  • Bob picks the second character of string  and adds it to the end of string . Thus, the strings are = bb= a, and = a .
  • Alice picks the second character of string  and adds it to the end of string . Thus, the strings are = b= ab, and = a .
  • Bob picks the first character of string  and adds it to the end of string . Thus,  becomes empty, = ab, and = ab .

We can see that using this sequence of moves, the final strings  and  are equal.

Test case 2: There exists no sequence of moves such that the strings  and  become equal in the end.

Test case 3: There exists no sequence of moves such that the strings  and  become equal in the end.

Test case 4: Consider the following sequence of moves:

  • Alice picks the first character of string  and adds it to the end of string . Thus,  becomes qprqr and  becomes p.
  • Bob picks the second character of string  and adds it to the end of string . Thus, the strings are = qrqr= p, and = p .
  • Alice picks the second character of string  and adds it to the end of string . Thus, the strings are = qqr= pr, and = p .
  • Bob picks the third character of string  and adds it to the end of string . Thus,  becomes qq becomes pr, and  becomes pr.
  • Alice picks the second character of string  and adds it to the end of string . Thus, the strings are = q= prq, and = pr .
  • Bob picks the first character of string  and adds it to the end of string . Thus,  becomes empty, = prq, and = prq .

We can see that using this sequence of moves, the final strings  and  are equal.


Code(c++):-

#include <iostream>
using namespace std;

int main() {
    // your code goes here
    int t;
    cin>>t;
    while(t--)
    {
     int n;
     cin>>n;
     string s;
     cin>>s;
     if(n%2!=0)
     cout<<"NO"<<endl;
     else
     {
     int fre[26]={0};
     for(int i=0;i<n;i++)
     {
     fre[s[i]-97]+=1;
     }
     int flag=0;
     for(int i=0;i<26;i++)
     {
     if(fre[i]%2!=0)
     {
     flag=1;
     break;
     }
     }
     if(flag==0)
     cout<<"YES"<<endl;
     else
    
     cout<<"NO"<<endl;
     }
    }
    return 0;
}

Recommended Post :-

HCL Coding Questions:-

Capgemini Coding Questions:-

Companies interview:-

Full C course:-    

Key points:-

Cracking the coding interview:-

 Array and string:-

Tree and graph:-

Hackerearth Problems:-

Hackerrank Problems:-

Data structure:-

 MCQs:-