[leetcode 75] 409. Longest Palindrome

문제해석

소문자 혹은 대문자로 이루어진 문자열 s가 주어졌을 때 가장 긴 palindrome 문자열을 만들수 있는 길이를 반환

문자들은 대소문자를 구분한다 예를들어 "Aa"는 palindrome이 아니다.

 

정답 예

public int longestPalindrome(String s) {
    int[] chars = new int[128];

    // 각 character를 아스키코드로 저장 후 횟수를 기억
    for (int i=0; i<s.length(); i++) {
        chars[s.charAt(i)]++;
    }

    int longestPalindromeLength = 0;
    int longestOdd = 0;
    for (int i=0; i<chars.length; i++) {
        // 문자열이 짝수 개 있는 경우 그대로 저장
        if (chars[i]%2 == 0) {
            longestPalindromeLength += chars[i];
        } else {
            // 가장 긴 홀수 문자 수 기억
            longestOdd = chars[i];

            // 홀수로 주어진 문자는 최대한의 짝수개 만큼만 사용
            longestPalindromeLength += chars[i] - 1;
        }
    }

    // 홀수 문자열이 하나라도 존재 하는 경우 가운데 위치시킬 홀 수 문자하나 더하기
    if (longestOdd > 0) {
        longestPalindromeLength++;
    }

    return longestPalindromeLength;
}