- Practice
- Algorithms
- Strings
- Game of Thrones - I
- Discussions

# Game of Thrones - I

# Game of Thrones - I

YaMogu + 30 comments If you are stuck you can follow this logic:

If len(str) is even, count of each elemnt should be even.

If len(str) is odd, count of ONLY one element should be odd, counts of all other elements should be even.

mosadev + 7 comments but, what about the string, aaabbb, it is a palindrome with a's odd and b's odd. can someone explane the approche.

YaMogu + 3 comments aaabbb is not a palindrome, as aaabbb != bbbaaa. :) Let me explain the approach a bit further. Let's say we have a string abcxyz. If it's a palindrome, than a =z , b=y, c = x. So we have a string abccba. So we have a pair of each elements. Which means if the len of the string is even => there is at least one pair of each element hence the count of each element should be even. But if the len of the string is odd it means in the middle of the string there should be one and only one unpaired element. So, the count of ONLY one element should be odd.

kajoljain + 0 comments thnkuuu ur explaination is really helpful... :)

dipple + 0 comments Then why is my testcases failing here? Does the execution has problem?

smartdeeps18 + 0 comments abbabba bbaaabb and so on........

breeze1823 + 0 comments Bro your question is wrong,its,aaabbbb

jjlearman + 2 comments There is even simpler logic, along the same lines, though it takes one more mental step to prove it. There's no need to test whether the string length is odd or even. The correctness test is a little different than yours, of course.

arbetts + 0 comments here's the proof:

even + even = even

odd + odd = even

odd + even = oddif the string length is even then it must have an even number of odd substrings, meaning 0, 2, 4... Otherwise the length would be odd.

this means that a correct test for the odd length should also catch valid even length strings.

rishabh_jaiswal1 + 0 comments Can you please explain if not?

player786 + 4 comments No need to check whether the length of string is even or odd, the second condition i.e. count of ONLY one element should be odd will be enough.

pawan1650 + 0 comments i didn't get it, can you explain it?

przyp_marek + 1 comment I have just counted occurence of each letter, and than i summed up numberOfCharOccurrence % 2; if it was greater thatn 1 than we can't have a palindrome of the strin;

ssepiol123 + 0 comments what about string aaabbb

ganeshran + 4 comments But the Dothraki never cross the seas. How did they invade Westeros?

I kid.. I kid

shayne93 + 0 comments HaHa, but khaleesi will be back !!

alienxx + 0 comments Dragons!

meg_mitchell + 1 comment I was more surprised that Robert managed to sober up long enough to figure out what a palindrome is. :)

JJJason + 0 comments LOL

dfoianu + 1 comment Here's a more in-depth explanation of the counting solution.

The problem asks you to divide a string into two mirrored parts. For example:

[abababab]

[aabb][bbaa]

A letter in the string can appear an odd or an even number of times. Let's consider what happens when the number of letters that appears an odd number of times varies.

0 "odd letters":

[aabbaabb]

[----][----]

Each letter on the left side must have a pair on the right side. If the number is even, it means we can definitely divide this string into two mirrored parts, as each letter does have a pair.

1 "odd letters":

[aabbaabbccc]

[----]ccc[----]

c[----]c[----]c

When we have 1 "odd" letter, the string can only be a palindrome if the letter without a pair is in the middle, between the two mirrored parts. Therefore, we can make a palindrome in this case.

2 or more "odd letters":

[aabbaabbcccddd]

[----]ccc[----]

c[----]c[----]c

In the case of one "odd" letter, we can put the unpaired one in the middle. But we only have one middle, so if the number of "odd" letters is any higher than 1, there is no possible position we can put the second "odd" letter and still have the string be a palindrome.hthakur98 + 1 comment You guys got way too much free time :/

h1552374764 + 0 comments So free that we've decided to become software engineers

johnbanner + 2 comments bit shifting is fun :)

int main() { string s; cin>>s; int flag = 0; uint64_t mask = 0x0; for (int i = 0; i < s.length(); i++) mask = mask ^ (1 << (s[i]-'a')); if ((!mask) || (((mask & (mask - 1)) == 0))) flag = 1; if(flag==0) cout<<"NO"; else cout<<"YES"; return 0; }

shubhamitankr + 1 comment elaborate .. plz?

johnbanner + 1 comment *Figure out whether any anagram of the string can be a palindrome or not.*A palindrome of even length should have all character counts even. A palindrome of odd length should have all but one character counts even.

the given input string contains only lower case english letters, which are 26 of them. I am masking the bits for each character occurences.

let me take an example:

- Even length palindrome:
**abba**:- Here we have 2 occurences of 'a' and 'b'.- s[0] == 'a':- enables bit 1. => mask: 00000000000000000000000001
- s[1]== 'b' :- enables bit 2. => mask: 00000000000000000000000011
- s[2]== 'b' :- if bit is enabled then XOR disable it. => mask: 00000000000000000000000010
- s[3]== 'a' :- if bit is enabled then XOR disables it. => mask: 00000000000000000000000000

- Odd length palindrome:
**abcba**:- Here we have 2 occurneces of 'a' and 'b' and one occurence of 'c'.- s[0] == 'a':- enables bit 1. => mask: 00000000000000000000000001
- s[1]== 'b' :- enables bit 2. => mask: 00000000000000000000000011
- s[2]== 'c' :- enables bit 3. => mask: 00000000000000000000000111
- s[3]== 'b' :- if bit is enabled then XOR disable it. => mask: 00000000000000000000000101
- s[4]== 'a' :- if bit is enabled then XOR disable it. => mask: 00000000000000000000000100

If our given string is even length palindrome then "mask" will always be zero going by above logic.

If our given string is odd length palindrome then "mask" will always be power of 2 (to check if given integer is power of 2 :-> (n & (n - 1) == 0)).

hope it helps.

shubhamitankr + 0 comments yup , got it.. thanks for help.

- Even length palindrome:

abhishek_falmari + 0 comments It worked! Thanks.

SameerRaj + 0 comments In pallindrome,it is simple the count of no of occurrence of a alphabet in string should be even. One and only one alphabet(any alphabet) can have odd count.

If any string that dont follow this rule cannot be converted into a pallindrome.

Sort 689 Discussions, By:

Please Login in order to post a comment