Grokking the Coding Interview: Patterns for Coding Questions

0% completed

​

Problem 4: Longest Palindrome(easy)

Problem Statement:

Given a string, determine the length of the longest palindrome that can be constructed using the characters from the string. You don't need to return the palindrome itself, just its maximum possible length.

Examples:

    • Input: "applepie"
    • Expected Output: 5
    • Justification: The longest palindrome that can be constructed from the string is "pepep", which has a length of 5. There are are other palindromes too but they all will be of length 5.
    • Input: "aabbcc"
    • Expected Output: 6

.....

.....

.....

Like the course? Get enrolled and start learning!
Elena Feoktistova

Elena Feoktistova

· 3 years ago

import java.util.HashMap;

public class Solution {
    public int longestPalindrome(String s) {
        int length = 0;
        Map<Character, Boolean> map = new HashMap<>();

        for (Character ch: s.toCharArray()) {
            if (map.get(ch) != null) {
                map.remove(ch);
                length += 2;
            } else {
                map.put(ch, Boolean.TRUE); 
            }
        }

        return map.isEmpty() ? length : ++length;
    }
}
Saman Ehsan

Saman Ehsan

· 3 years ago

According to the explanation, as the input string grows, the size of the hashmap will be at most the number of unique characters in the alphabet being used. So wouldn't that be O(1) space because the size of the hashmap does not grow linearly as the input scales?

Show 2 replies
T

Tony Pham

· 2 years ago

For this example:

print(sol.longestPalindrome("applepie")) # Expected output: 7

expected outcome should be 5 not 7.

D

designgurus

· a year ago

class Solution:
    def longestPalindrome(self, s: str) -> int:    
        charFreq = Counter(s)
        result = 0
        for char in set(s):
            if charFreq[char] % 2 == 1:
                result += charFreq[char] - 1
            else:
                result += charFreq[char]
            
        return result + 1 if (len(s) - result) >= 1 else result
Modestas Filipavicius

Modestas Filipavicius

· 7 months ago

class Solution:
    def longestPalindrome(self, s: str) -> int:      
        length = 0

        # count all the chars
        ct = {}
        for c in s:
            ct[c] = ct.get(c, 0) + 1

        # flag counter to see how many odd counts detected
        odd_detected = 0

        # traverse the set of chars
        for char in set(s):
    
            if ct[char] % 2 == 0:
                # even count, increment length
                length += ct[char]
            elif ct[char] % 2 == 1 and ct[char] > 2:
                # odd count is > 2, tally up as if it was odd count, but increment the flag
                # needed when s = 'xxxyyy'
                length += ct[char] - 1
                odd_detected += 1
            else:
                # odd count == 1, increment fla
Quốc Phong Trần

Quốc Phong Trần

· 23 days ago

from collections import defaultdict
class Solution:
    def longestPalindrome(self, s: str) -> int:      
        length = 0
        # ToDo: Write Your Code Here.        
        m = defaultdict(int)
        for c in s:
            m[c] += 1
        for c in m:
            if m[c] >= 2:
                length += m[c] - (m[c] % 2)
        return length if length == len(s) else length + 1