Longest Palindrome - Leetcode 409 - Python

[@no.cereal2067]

For the second approach, we can slightly further optimize it by not using res variable but either returning the length of string s itself or length of string s - length of the set + 1
Imagine a case where string s doesn't have character of odd length at all. For example, aabbXXXX, as we remove each character every time it's even, we're left with empty set. But if there is an extra X and Z like aabbXXXXXZ, then we're left with a set {X, Z}. Notice that these extra two will cancel out from original string or you may think of them as unnecessary characters and then we need to add it back by 1. Hope it helps!

[@asagiai4965]

Haven't seen your solution yet.
Though I noticed. The number (count/occurrence) of a character.
Can help determine if you can use that character as part of the palindrome.
Especially if their count is divisible by 2 or is 1
Updated: or 1 (odd)

[@HPan-sx9bw]

This is my solution :
1. Add all characters that have even occurrence
2. For all those characters where occurrence is odd, find the one with max count
3. For rest of all odd characters , subtract 1 and add to final count
class Solution:
def longestPalindrome(self, s: str) -> int:
count=0
oddarr=[0]
for i in set(s):
if s.count(i) %2 ==0:
#point 1 explained
count = count+s.count(i)
else:
oddarr.append(s.count(i))
oddarr = sorted(oddarr)
#point 2 explained
count = count + oddarr.pop()
for i in oddarr:
if i>0:
#point 3 explained
count = count + i -1
return count

[@mohamedzaheen3246]

Happy to see your c++ code 😊

[@weiss7070]

It's 4 a.m., and I can't sleep because there's a fly buzzing around, and now i watching leetcode problems nice

[@RubyVA-gx4cd]

It's 5 am and I am sitting on my PC solving leetcodes since 4 am, good luck to you guys)

[@mohammedsuhail.s192]

class Solution:
def longestPalindrome(self, s: str) -> int:
k=Counter(s)
count=0
flag=False
for i,j in k.items():
if j%2==0:
count+=j
else:
count+=j-1
flag=True
if flag:
return count+1
return count

[@mohamedanas8493]

what a coincidence
class Solution:
def longestPalindrome(self, s: str) -> int:
hashmap={}
for i in s:
if i not in hashmap:
hashmap[i]=1
else:
hashmap[i]+=1
print(hashmap)
count=0
flag=False
for i in hashmap:
if hashmap[i]%2==0:
count+=hashmap[i]
else:
count+=hashmap[i]-1
flag=True
if flag:
return count+1
return count

[@sachethkoushik2265]

arrived at the same soln loll

[@mohammedsuhail.s192]

@@mohamedanas8493

[@Boodiez]

Easy Solution
class Solution:
def longestPalindrome(self, s: str) -> int:
cnt = Counter(s)
odd = 0
res = 0
for c in cnt:
if cnt[c] % 2 != 0:
odd = 1
res = res + (cnt[c] // 2 * 2)

return res + odd

[@jeet9361]

class Solution:
def longestPalindrome(self, s: str) -> int:
l=[0]*70
for i in s:
l[ord(i)-ord('A')] += 1
s=0
for i in l:
if i%2==0:
s=s+i
else:
s=s+i-1
if s==sum(l):
return s
else:
return s+1

[@armantavakoli5314]

DAYUM CLEAN

[@pastori2672]

id love to see you code the next one in C++

[@gauravsati1041]

Great explanation

[@TUPEBYDLO]

No need to check for odd number of characters or if set is not empty for the second solution - just if your result is less than input length, then you can always increment the result number

[@TenzDelek]

bro opens my third eye

[@kthtei]

What a great approach. I just watched the explanation part and tried to come up with my own code here.
class Solution:
def longestPalindrome(self, s: str) -> int:
hashmap = Counter(s)
length = 0
odd = False
for v in hashmap.values():
if v % 2 == 0:
length += v
else:
odd = True
length += v - 1

return length + 1 if odd else length
Using set is pretty much super optimized version, but I'm not sure if I can come up with that solution lol.

[@tcookiem]

You can just do length + odd

[@mitchelsonbrooks]

In the example you gave of aabbbccc. Couldn't you arrange it as bbbaaccc. length of 8? But I believe your solution would return 7. Am I missing something?

[@BroodWar4Ever]

Remember, a palindrome is a word (string) that reads the same forwards and backwards. bbbaaccc is not a palindrome because bbbaaccc != cccaabbb

[@mitchelsonbrooks]

@@BroodWar4Ever ooops! great catch haha. thank you :)

[@ArunKumar-gx8iv]

Easy solution
public int longestPalindrome(String s) {
int ans = 0;
int[] count = new int[128];
for (char c : s.toCharArray()) {
count[c]++;
}
boolean hasOdd = false;
for (int v : count) {
if (v % 2 == 0) {
ans += v;
} else {
ans += v - 1;
hasOdd = true;
}
}
return hasOdd ? ans + 1 : ans;
}

[@theteacher010]

I believe the time complexity for the solution here is O(3n), because in the worst case, for each char in the string, you are both adding it to the set once and deleting it from the set once.
The 2-pass solution that involves using a Hash-set to count values of each character on the other hand is only O(2n).
Not that it matters much of course!

[@dvalley56]

Where n is ?

[@sabukuna]

hello mr neet, my sikh bratha

[@chien-yuyeh9386]

First 🤩

[@samuraijosh1595]

int hash(char k){
if (k - 'a' >= 0) return k - 'a';
return k - 'A' + 26;
}
int longestPalindrome(char* s) {
int hashTable[52] = {0};
int res = 0;
int flag = 0;

for (int i = 0; s[i] != '\0'; i++){
hashTable[hash(s[i])] += 1;
}

for (int i = 0; i < 52; i++){
flag = hashTable[i] % 2 != 0 ? 1 : flag;

if (hashTable[i] > 1){
int local = hashTable[i] % 2 == 0 ? hashTable[i] : hashTable[i] - 1;
res += local;
}
}

return res + flag;
}

[@Amadorse]

bro thks it's quite useful

[@taufiqrahman2363]

second