409. Longest Palindrome

문제 설명

대문자 혹은 소문자로 이루어진 문자열 s를 이용하여 만든 회문(대칭인 문자열)의 길이의 최대값을 구하시오. 대소문자를 구분하므로 "Aa"는 회문이 아니다.

출력 예시

접근 방법

첫번째 시도

문자열 내 모든 문자를 사용하지 않아도 된다는 점, 대칭인 경우, 문자의 순서가 변해도 회문의 길이는 일정하다는 점을 통해 짝수의 중복 문자 개수를 모두 더하고 홀수의 중복 문자 개수 -1 을 더한 후 (홀수 개수가 존재했다면) 최종적으로 1을 더하면 되지 않을까?

소스코드

class Solution {
public:
    int longestPalindrome(string s) {
        bool one_flag=false;
        int result=0;
        int cnt_letter[124]={0};
        for(auto ch:s){ cnt_letter[ch]++;}
        
        for(int i=65; i<123; i++){
            if(cnt_letter[i]>1) {
                if(cnt_letter[i]%2==0) result+=cnt_letter[i];
                else {
                    result+=cnt_letter[i]-1;
                    one_flag=true;
                }
            }
            else if(cnt_letter[i]==1) one_flag=true;
        }
        
        if(one_flag) result+=1;
        
        return result;
    }
};

돌아보기

배열을 하나씩 탐색할때 유용한 반복문

for(auto element:array)