[Leetcode]409. Longest Palindrome

📄 Description

Given a string s which consists of lowercase or uppercase letters, return the length of the longest palindrome that can be built with those letters.

Letters are case sensitive, for example, "Aa" is not considered a palindrome here.

Example 1:

Input: s = "abccccdd"
Output: 7
Explanation:
One longest palindrome that can be built is "dccaccd", whose length is 7.

Example 2:

Input: s = "a"
Output: 1

Example 3:

Input: s = "bb"
Output: 2

Constraints:

• 1 <= s.length <= 2000
• s consists of lowercase and/or uppercase English letters only.

🔨 My solution

💭 Questioning for solving problem

• palindrome의 기본 형태는 어떻게 이루어져야 하는가?
• 짝수개의 알파벳만 palindrome에 포함될 수 있는가? 홀수개의 알파벳은 어떻게 포함될 수 있는가?

Steps for soling problem

👉 palindrome의 기본 형태

• a와 b는 동일한 알파벳 and 동일한 개수로 구성되어야 한다.
• a와 b 사이에는 1개의 알파벳이 들어갈 수 있다.

👉 palindrome의 구성 방법

1. a와 b에 들어갈 수 있는 모든 알파벳 찾기
   • 알파벳의 개수>=2인 경우, palindrome의 a 와 b 파트에 들어갈 수 있다.
2. a와 b 사이에 들어갈 알파벳 찾기
   • 남은 알파벳 중 개수가 1개인 알파벳 1개만 palindrome에 포함될 수 있다.(p_len+=1)

💻 My Submission

class Solution:
    def longestPalindrome(self, s: str) -> int:
        count=Counter(s)
        p_len=0
        
        for alpha in count:
            if count[alpha]>=2:
                p_len+=(count[alpha]//2)*2
                count[alpha]%=2
        if 1 in count.values():
            p_len+=1
        return p_len

Complexity

• Time Complexity: O(n)
  For scanning the count which size is n.

• Space Complexity: O(n)
  For hast table count which has n keys and n elements.

💊 Other Solution - using set()

class Solution(object):
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: int
        """
        hash = set()
        for c in s:
            if c not in hash:
                hash.add(c)
            else:
                hash.remove(c)
        # len(hash) is the number of the odd letters
        return len(s) - len(hash) + 1 if len(hash) > 0 else len(s)

• set()을 사용하여 결과적으로 hash에 홀수개인 알파벳이 남도록 한다.
• 전체 s 길이에서 홀수개인 알파벳 개수, 즉 len(has)를 빼주고, 한 개를 더해준다.

References

• https://leetcode.com/problems/longest-palindrome/
• https://leetcode.com/problems/longest-palindrome/discuss/89614/python-simple-set-solution