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 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 thnkuuu ur explaination is really helpful... :)
dipple Then why is my testcases failing here? Does the execution has problem?
smartdeeps18 abbabba bbaaabb and so on........
breeze1823 Bro your question is wrong,its,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.
rishabh_jaiswal1 Can you please explain if not?
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?
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;
ssepiol123 what about string aaabbb
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
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.
Sort 689 Discussions, By:
Please Login in order to post a comment