leetcode: 409. Longest Palindrome

문제링크

배경지식

Palindrome

• 거꾸로 읽어도 제대로 읽은 것과 같은 문장을 의미한다.
• ex) "bcacb", "abba"
• Palindrome의 길이는 홀수, 짝수 모두 가능하며 홀수인 경우 정 가운데의 문자는 어느 것이든 상관없다는 특징이 있다.

풀이1

• 문자열을 구성하는 각 문자의 개수를 map에 저장한다.
• 문자의 개수가 짝수라면 전부 Palindrome에 적용할 수 있다.
• 홀수인 경우 1을 뺀 개수를 전부 Palinderome에 적용할 수 있다.
• 이 때, 문자의 개수가 홀수인 경우가 존재하면 Palinderome의 길이 역시 홀수로 만들 수 있기 때문에 1을 더해준다.

class Solution {
    fun longestPalindrome(s: String): Int {
        val letterMap = mutableMapOf<Char, Int>()
        for (letter in s) {
            var value = letterMap[letter]
            value = value ?: 0
            letterMap[letter] = value + 1
        }
        var length = 0
        var hasOdd = false
        for ((key, value) in letterMap) {
            if (value and 1 == 0)
                length += value
            if (value and 1 == 1) {
                hasOdd = true
                length += (value - 1)
            }
        }
        if (hasOdd)
            length++
        return length
    }
}

시간복잡도 : O(N)
공간복잡도 : O(N)

풀이2

• 문자열을 순회하며 문자가 집합에 있는 경우 count를 증가시키면서 집합의 원소를 삭제한다.
• 집합에 없는 경우 집합에 원소를 추가한다.
• 순회가 끝나면 Palindrome의 길이를 계산하기 위해 count에 2를 곱해주는데, 집합의 원소가 있는 경우 Palindrome의 길이가 홀수일 수 있는 경우이므로 1을 더해준다.

class Solution {
    fun longestPalindrome(s: String): Int {
        val hashSet = hashSetOf<Char>()
        var count = 0
        for (letter in s) {
            if (hashSet.contains(letter)) {
                count++
                hashSet.remove(letter)
            } else {
                hashSet.add(letter)
            }
        }
        if (!hashSet.isEmpty()) count = count * 2 + 1
        else count = count * 2
        return count
    }
}

시간복잡도 : O(N)
공간복잡도 : O(N)