Thursday 11 September 2014

Game of Thrones - I (check pelidnrome string)

King Robert has 7 kingdoms under his rule. He finds out from a raven that the Dothraki are soon going to wage a war against him. But, he knows the Dothraki need to cross the narrow river to enter his dynasty. There is only one bridge that connects both sides of the river which is sealed by a huge door.
door
The king wants to lock the door so that the Dothraki can't enter. But, to lock the door he needs a key that is an anagram of a certain palindrome string.
The king has a string composed of lowercase English letters. Help him figure out if any anagram of the string can be a palindrome or not.
Input Format  A single line which contains the input string
Constraints  1<=length of string <= 10^5  Each character of the string is a lowercase English letter.
Output Format  A single line which contains YES or NO in uppercase.
Sample Input : 01
aaabbbb
Sample Output : 01
YES
Explanation  A palindrome permutation of the given string is bbaaabb. 
Sample Input : 02
cdefghmnopqrstuvw
Sample Output : 02
NO
Explanation  You can verify that the given string has no palindrome permutation. 
Sample Input : 03
cdcdcdcdeeeef
Sample Output : 03
YES
Explanation  A palindrome permutation of the given string is ddcceefeeccdd .


#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
 
void findPalind(char *arr)
{
     
    int flag = 0,len,index,i,count,status[26]={};
    len=strlen(arr);
    for(i=0;i<len;i++)
    { index=(int)arr[i]-97;
      if(status[index]==0)
          status[index]=1;
      else status[index]=0;    
    } 
    count=0;
    for(index=0;index<26;index++)
    {
    if(count>1)
    {
     flag=1;
     break;   
    } 
    if(status[index]==1)
        count++;    
    }
    if (flag==0)
        printf("YES\n");
    else
        printf("NO\n");
    
    
}
int main() {

    char arr[100001];
    scanf("%s",arr);
    findPalind(arr);
    return 0;
}


No comments:

Post a Comment