We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.

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.

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")

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.

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;

@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.

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;
}

The condition checks to see if any letter appears an odd number of times. If so it will increment the count variable. You can have at most one letter appear an odd number of times - and this letter will then be the center of the palindrome.

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 :)

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.

fromcollectionsimportCounterdefgameOfThrones(s):# Complete this functionnum_odd=0s1=Counter(s)foreachins1.values():ifeach%2!=0:num_odd+=1# when num_odd > 1, not palindromeifnum_odd>1:return'NO'return('YES')

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.

## Game of Thrones - I

You are viewing a single comment's thread. Return to all 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.

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

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.

thnkuuu ur explaination is really helpful... :)

Then why is my testcases failing here? Does the execution has problem?

Bro your question is wrong,its,aaabbbb

hi String "aaabbb" is not palindrome . in the sample test case string is "aaabbbb" .

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")

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.

here's the proof:

even + even = even

odd + odd = even

odd + even = odd

if 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.

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.

i didn't get it, can you explain it?

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

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....

ok.. Thanks

how can u check that without determing the nature of lenth?pls explain

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;

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

This made it very easy to solve. Thanks for the tip!

Thank you. That was some "HINT".

yeah.. thanks guys .. for the hints

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

@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,

baabbaabhas an even length(8) as the length of lettersa&bis even(4) thus a palindrome. Likewiseaabaahas an odd length(5) but the length of letterais even(2) and only one odd charbthus a palindrome otherwise not. Hope this will easy comprehension.Good one with collections in python life is easy :D

C solution:

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

The condition checks to see if any letter appears an odd number of times. If so it will increment the count variable. You can have at most one letter appear an odd number of times - and this letter will then be the center of the palindrome.

k

Bc who's look like qus format

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

through this loop i think he in determining the no. of occurance of each alpabat....

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

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

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

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

This is exactly what I did.

Thanks. This worked nicely with c++ bitsets and use of flip function.

More optimized code implementation here .

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.

Great solution!

nice one;)

you can use set also:

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

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 :)

Great idea...

Excellent approach..

why can't i implement the same using ArrayList?

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

your logic is not correct in all cases

Thnx man..really usefull..but..already revealed solution so no points counted!..

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.

that's good... i'll try it

This is basically an "if you're stuck, this is the answer."

thank you sir....

this could be considered one liner in python,

can you please explain this as I am new to python and I find your solution way better than mine

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.

I came to the same on my own. This is my implementation in Python3:

Thank you :)

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

That looks a lot like the Haskell solution:

done the same code but test case fails for large string