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

# Game of Thrones - I

# Game of Thrones - I

YaMogu + 28 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 + 5 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 + 0 comments [deleted]YaMogu + 2 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.

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

viveksr89 + 0 comments hi String "aaabbb" is not palindrome . in the sample test case string is "aaabbbb" .

pg170898 + 0 comments s = input() s = list(s) liss = [0]26 for char in s: if(liss[ord(char)-ord('a')]==0): liss[ord(char)-ord('a')]+=1 else: liss[ord(char)-ord('a')]-=1 total = sum(map(abs,liss)) if(total<=1): print("YES") else: print("NO")

jjlearman + 1 comment 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.

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?

ansul90 + 1 comment In case of aaaabbbb none of the elements have odd occurrence but it has a valid palindrome bbaaaabb.

kajoljain + 2 comments ya thats the logic....if all elements occur even time then its palindrone.....nd for odd max one aplhabate can have odd no. of occurance....

ansul90 + 0 comments ok.. Thanks

arnav_agyeya + 0 comments how can u check that without determing the nature of lenth?pls explain

przyp_marek + 0 comments 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;

yo9rtace + 0 comments But I think if you have the condition of string, you can return 'NO' in the loop of the function earlier.

Schuetzl + 0 comments This made it very easy to solve. Thanks for the tip!

TheEEnsane + 1 comment Thank you. That was some "HINT".

dheerajvatti + 0 comments yeah.. thanks guys .. for the hints

KonshensX + 1 comment i still haven't figured out how am i supposed to count each element and checking if the count is even or not .

candi3114 + 0 comments @KonshensX with the count you figure out if a given input is a palindrome or not. Just understand the logic and implement it. It make it easier. That was very smart @YaMogu. Thanks for the hint.

To be more practical,

**baabbaab**has an even length(8) as the length of letters**a**&**b**is even(4) thus a palindrome. Likewise**aabaa**has an odd length(5) but the length of letter**a**is even(2) and only one odd char**b**thus a palindrome otherwise not. Hope this will easy comprehension.

candi3114 + 0 comments Good one with collections in python life is easy :D

etayluz + 4 comments C solution:

`void findPalind(char *arr) { int flag = 0; // Find the required answer here. Print Yes or No at the end of this function depending on your inspection of the string int letter[26] = {0}; for (int i = 0; i < strlen(arr); i++) { letter[arr[i] - 'a']++; } int count = 0; for (int i = 0; i < 26; i++) { if (letter[i] % 2 == 1) { count++; } } if (count > 1) { flag = 1; } if (flag==0) printf("YES\n"); else printf("NO\n"); return; } int main() { char arr[100001]; scanf("%s",arr); findPalind(arr); return 0; }`

Maheboob + 2 comments why this 'if (letter[i] % 2 == 1)' and why not this 'if (letter[i] % 2 == 0)'

naveenchopra933 + 0 comments Bc who's look like qus format

santhakumarkrish + 1 comment for (int i = 0; i < strlen(arr); i++) { letter[arr[i] - 'a']++; } can you explain this logic

kajoljain + 0 comments through this loop i think he in determining the no. of occurance of each alpabat....

Pravesh_Jain + 0 comments Your way of finding the count of each letter is brilliant. I initially used nested loops which resulted in time out.

leech932 + 0 comments You can optimize it a bit more by removing the if clause inside your second for loop.

for (x=0;x<26;x++) { odds += (lettercounts[x]&1); }

I just check if odds > 1. Not huge but eliminating conditionals boosts performance quite a bit.

allano + 1 comment Or this logic: Maximum one element can have odd count, counts of rest elements should be even.

umejiamartinez + 0 comments This is exactly what I did.

51n15t9r + 2 comments Thanks. This worked nicely with c++ bitsets and use of flip function.

`string s; cin>>s; int flag = 0; bitset<26> bs(std::string("00000000000000000000000000")); for(int i = 0 ; i < s.size(); i++) { bs.flip(s[i]-'a'); } if((s.size() % 2 !=0) && (bs.count() == 1)) { flag = 1; } else if ((s.size() %2 == 0) && (bs.count() == 0)) { flag = 1; } if(flag==0) cout<<"NO"; else cout<<"YES"; return 0;`

shahed_shd + 0 comments [deleted]shahed_shd + 0 comments More optimized code implementation here .

peterkirby + 1 comment Using parity bits in a single integer was a fun way to do this in C++. Here a 0 bit is even, a 1 bit is odd.

`int main() { string s; cin >> s; int parity = 0; for (char ch : s) parity ^= 1 << (ch - 'a'); cout << (__builtin_popcount(parity) <= 1 ? "YES" : "NO") << endl; return 0; }`

VictoriaB + 0 comments Great solution!

arunkumarg18 + 0 comments nice one;)

aahd88 + 5 comments you can use set also:

`Scanner scan = new Scanner(System.in); String str = scan.nextLine(); Set<Character> set = new HashSet<Character>(); for(Character ch : str.toCharArray()){ if(set.contains(ch)){ set.remove(ch); }else{ set.add(ch); } } System.out.println((set.size()<=1)?"YES":"NO"); scan.close();`

ThomasHolz + 1 comment Thanks, I forgot about Set and used a Map instead with a dummy value variable.

logesh_lohit + 0 comments [deleted]

hvas89 + 0 comments My solution is similar, but I added a condition at the beginning of the loop to make it quit as soon as we know there is no chance for it to be a palindrome :)

HashSet<Character> hashSet = new HashSet<Character>(); for(int i=0;i<word.length();i++){ if(hashSet.size() > (word.length()-i) + 1) return false; char character = word.charAt(i); if(hashSet.contains(character)){ hashSet.remove(character); }else{ hashSet.add(character); } } return hashSet.size() == word.length()%2;

logesh_lohit + 0 comments Great idea...

stranger400 + 0 comments Excellent approach..

judealphonsesav1 + 0 comments why can't i implement the same using ArrayList?

GThack + 0 comments Actually you only need the second check because there can not be a case where the lenght is even and only one element is odd

rwan7727 + 0 comments [deleted]mr__cool + 0 comments your logic is not correct in all cases

breeze1823 + 0 comments Thnx man..really usefull..but..already revealed solution so no points counted!..

JJJason + 0 comments Merge odd and even situations. That means regardless the len(str) is odd or even, just when the count of each elements have no more than ONE, the str is palindrome.

from collections import Counter def gameOfThrones(s): # Complete this function num_odd = 0 s1 = Counter(s) for each in s1.values(): if each % 2 != 0: num_odd += 1 # when num_odd > 1, not palindrome if num_odd > 1: return 'NO' return ('YES')

anushagandhi1996 + 0 comments that's good... i'll try it

firefly2002 + 0 comments This is basically an "if you're stuck, this is the answer."

sharatmalkhed + 1 comment [deleted]sharatmalkhed + 0 comments thank you sir....

alexdatavault + 1 comment this could be considered one liner in python,

def gameOfThrones(s): return 'YES' if sum([1 for i in "abcdefghjkilmnopqrstuvwxyz" if i in s if sum([1 for j in s if i==j])%2==1]) <=1 else 'NO'

18BCS6626 + 0 comments can you please explain this as I am new to python and I find your solution way better than mine

tanay2000 + 0 comments Or you can just have simple logic. A string to be formed as palindrome we should have only 1 character which has odd number of counts and other should have even number of counts.

hellomici + 0 comments I came to the same on my own. This is my implementation in Python3:

from collections import Counter def gameOfThrones(s): counter = Counter(s) middle = 0 if not len(s) // 2: # even for k,v in counter.items(): if v // 2: return "NO" else: for k,v in counter.items(): if v % 2 == 1: middle += 1 if middle > 1: return "NO" return "YES"

sheetansh + 0 comments from collections import Counter def gameOfThrones(s): c = dict(Counter(s)) odd = 0 for i in c.values(): if i % 2 != 0: odd+=1 if odd > 1: return "NO" return "YES"

SI005239_Mahi + 0 comments Thank you :)

mike_buttery + 1 comment Use dictionary comprehension and

`s.count()`

Map modulo two across the counts, odd = 1, even = 0, summing the result

If there is more than one odd result cannot be a palindrome

d = {c:s.count(c) for c in set(s)} if sum(map(lambda x: x%2, d.values())) > 1: return 'NO' return 'YES'

Widget + 0 comments That looks a lot like the Haskell solution:

import Data.List(sort, group) main = interact isAnaPalin isAnaPalin s = if (length $ filter id $ map (odd . length) $ group $ sort s) > 1 then "NO" else "YES"

Vikas_Dalal_Nsit + 0 comments done the same code but test case fails for large string

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

erich_kramer1 + 0 comments I have some bad news friend.

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.

trendsetter37 + 3 comments I was wondering if there are really no other submissions in Lisp. If I go to the leaderboard it informs me that it is awaiting more submissions before producing a leaderboard.

abhiranjan + 0 comments There are two options:

- Be a true trendsetter
- Or try some problems from fp section.

abhiranjan + 0 comments Ohh, there are already some submissions there for lisp. Though we don't have any submission in racket, which is recently added, till now.

trendsetter37 + 0 comments Ohh ok got it. I am new here and totally forgot about the fp section. Thanks for the clarification though on using sbcl.

__spartax + 2 comments from collections import Counter print "YES" if len(filter(lambda x: x & 1, Counter(raw_input()).values())) <= 1 else "NO"

shankwiler + 1 comment similarly,

`s = input().strip() if len([c for c in set(s) if s.count(c) % 2 != 0]) < 2: print('YES') else: print('NO')`

dm_dubovitsky + 1 comment you use

`set(s)`

in the loop, so it is unnessary workerich_kramer1 + 1 comment Is it evaluated every

dm_dubovitsky + 0 comments Sure (has not), my bad

erich_kramer1 + 1 comment one line, can you golf it more? ;)

return (sum(s.count(x)%2 for x in set(s) ) <2 and 'YES') or 'NO'

Widget + 0 comments Without using sets (and in Haskell, not Python):

isAnaPalin = bool "YES" "NO" . (>1) . length . filter id . map (odd . length) . group . sort

I'm sure it's possible to do a lot better than that though.

Majka + 0 comments If there is more than 1 letter that occurs odd number of times then there is no anagram.

int main(){ char *s = (char*)malloc(100001); scanf("%s",s); int arr[26] = {0}; int l = strlen(s); for(int i = 0; i < l; i++){ arr[s[i]-97]++; } int countOdd = 0; for(int i = 0; i < 26; i++){ if(arr[i] % 2 == 1) countOdd++; if(countOdd > 1){ printf("NO"); break; } if(i == 25) printf("YES"); } return 0; }

ctrs1 + 0 comments Python 3 solution:

def gameOfThrones(s): d = {} for i in s: d[i] = d.get(i, 0) + 1 return('YES' if sum(i % 2 for i in d.values()) < 2 else 'NO')

In a palindrome, only 1 character at most can appear an odd number of times.. If more than 1 character appears an odd number times, we return

`'NO'`

,

sid05182000 + 1 comment Python 3:

from collections import Counter if len([1 for x in Counter(input()).values() if x & 1]) <= 1: print('YES') else: print('NO')

advaithsurya + 0 comments Nisee...

Sort 524 Discussions, By:

Please Login in order to post a comment