Header Ads Widget

String Game || codechef solution

Rajnish Tripathi 05:30

 

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 YES, yEs, yes, and yeS will all be treated as identical).

Constraints

  • 1≤�≤103
  • 1≤�≤105
  • � consists of lowercase english alphabets
  • The sum of � over all test cases does not exceed 2⋅105.

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:-


Tags:

Post a Comment

0 Comments