YaMogu 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 but, what about the string, aaabbb, it is a palindrome with a's odd and b's odd. can someone explane the approche.
YaMogu [deleted]YaMogu 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 Bro your question is wrong,its,aaabbbb
viveksr89 hi String "aaabbb" is not palindrome . in the sample test case string is "aaabbbb" .
jjlearman 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 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 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 i didn't get it, can you explain it?
ansul90 In case of aaaabbbb none of the elements have odd occurrence but it has a valid palindrome bbaaaabb.
kajoljain 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 ok.. Thanks
arnav_agyeya how can u check that without determing the nature of lenth?pls explain
przyp_marek 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 But I think if you have the condition of string, you can return 'NO' in the loop of the function earlier.
Schuetzl This made it very easy to solve. Thanks for the tip!
TheEEnsane Thank you. That was some "HINT".
dheerajvatti yeah.. thanks guys .. for the hints
KonshensX i still haven't figured out how am i supposed to count each element and checking if the count is even or not .
candi3114 @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 Good one with collections in python life is easy :D
etayluz 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 why this 'if (letter[i] % 2 == 1)' and why not this 'if (letter[i] % 2 == 0)'
naveenchopra933 Bc who's look like qus format
santhakumarkrish for (int i = 0; i < strlen(arr); i++) { letter[arr[i] - 'a']++; } can you explain this logic
kajoljain through this loop i think he in determining the no. of occurance of each alpabat....
Pravesh_Jain Your way of finding the count of each letter is brilliant. I initially used nested loops which resulted in time out.
leech932 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 Or this logic: Maximum one element can have odd count, counts of rest elements should be even.
umejiamartinez This is exactly what I did.
51n15t9r 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 [deleted]shahed_shd More optimized code implementation here .
peterkirby 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 Great solution!
arunkumarg18 nice one;)
aahd88 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 Thanks, I forgot about Set and used a Map instead with a dummy value variable.
logesh_lohit [deleted]
hvas89 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 Great idea...
stranger400 Excellent approach..
judealphonsesav1 why can't i implement the same using ArrayList?
GThack 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 [deleted]
mr__cool your logic is not correct in all cases
breeze1823 Thnx man..really usefull..but..already revealed solution so no points counted!..
JJJason 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 that's good... i'll try it
firefly2002 This is basically an "if you're stuck, this is the answer."
sharatmalkhed [deleted]sharatmalkhed thank you sir....
alexdatavault 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'
tanay2000 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 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"
ganeshran But the Dothraki never cross the seas. How did they invade Westeros?
I kid.. I kid
shayne93 HaHa, but khaleesi will be back !!
alienxx Dragons!
meg_mitchell I was more surprised that Robert managed to sober up long enough to figure out what a palindrome is. :)
JJJason LOL
erich_kramer1 I have some bad news friend.
dfoianu 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 You guys got way too much free time :/
h1552374764 So free that we've decided to become software engineers
johnbanner 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 elaborate .. plz?
johnbanner 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 yup , got it.. thanks for help.
- Even length palindrome:
abba :- Here we have 2 occurences of 'a' and 'b'.
abhishek_falmari It worked! Thanks.
SameerRaj 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 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 There are two options:
- Be a true trendsetter
- Or try some problems from fp section.
abhiranjan 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 Ohh ok got it. I am new here and totally forgot about the fp section. Thanks for the clarification though on using sbcl.
__spartax from collections import Counter print "YES" if len(filter(lambda x: x & 1, Counter(raw_input()).values())) <= 1 else "NO"
shankwiler 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 you use
set(s)in the loop, so it is unnessary workerich_kramer1 Is it evaluated every
dm_dubovitsky Sure (has not), my bad
erich_kramer1 one line, can you golf it more? ;)
return (sum(s.count(x)%2 for x in set(s) ) <2 and 'YES') or 'NO'
Majka 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; }
Hemdan C++ Solution :
#include <iostream> #include <cmath> #include <string> #include <string.h> #include <stdlib.h> #include <algorithm> #include <iomanip> #include <assert.h> #include <vector> #include <cstring> #include <map> #include <deque> #include <queue> #include <stack> #include <sstream> #include <cstdio> #include <cstdlib> #include <ctime> #include <set> #include <complex> #include <list> #include <climits> #include <cctype> #include <bitset> #include <numeric> #include<array> #include<tuple> #include <utility> #include <functional> #include <locale> using namespace std ; int main() { string s ; cin >> s ; sort(s.begin(),s.end()) ; vector<int> v ; int counter = 1 ; int flag = 0 ; for(int i=0 ; i<s.size();i++) { if(s[i]==s[i+1]) counter++ ; else { if(counter%2!=0) flag++ ; counter = 1 ; } } (flag>1) ? cout << "NO" << endl : cout << "YES" << endl ; }
prasadraju_chek1 how you approached to this solution
Hemdan Before my approach we called string Palindrome either all its chars repeate even number of times or all its characters repeate even number of times except one element
This is My approach : when we sort the array , so we can know number of char^s which repeated odd numer of time (flag in my solution)
Srivatsav_0104 Java solution:-
static void gameOfThrones(String s) { int i,freq,count=0,even=0,odd=0; char ch; boolean flag = false; HashSet<Character> set = new LinkedHashSet(); for(i=0;i<s.length();i++) set.add(s.charAt(i)); ArrayList<Character> al = new ArrayList(); for(i=0;i<s.length();i++) al.add(s.charAt(i)); for(Object o:set) { ch = (char)o; freq = Collections.frequency(al, ch); if(s.length()%2==0) { if(freq%2!=0) { flag = false; break; } else { flag = true; continue; } } else { if(freq%2==0) even++; else odd++; } if(even==set.size()-1) flag=true; else flag=false; } if(flag==false) System.out.println("NO"); else System.out.println("YES"); }
rajhere hi.. check out my java solution..would be simpler..hope it will be helpfull :) https://www.hackerrank.com/challenges/game-of-thrones/forum/comments/432117
Sort 451 Discussions, By:
Please Login in order to post a comment