Longest Palindrome - Leetcode 409 - Python

0:00 - Read the problem
0:30 - Drawing Explanation
6:57 - Coding Explanation

leetcode 409

#neetcode #leetcode #python

[no.cereal]

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

[HPan-sxbw]

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

[asagiai]

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)

[weiss]

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

[mohammedsuhail.s]

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

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

[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

[pastori]

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

[jeet]

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

[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

[theteacher]

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!

[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?

[ArunKumar-gxiv]

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

[samuraijosh]

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