Leetcode - 1400. Construct K Palindrome Strings

문제

주어진 문자열에서 거꾸로 읽어도 동일한 문자열이 되는 palindrome 이 k개 만들어질 수 있는지 확인하는 함수를 작성하라.

Input: s = "annabelle", k = 2
Output: true
Explanation: You can construct two palindromes using all characters in s.
Some possible constructions "anna" + "elble", "anbna" + "elle", "anellena" + "b"

https://leetcode.com/problems/construct-k-palindrome-strings/

해결

아래와 같은 성질을 구현

• s의 길이가 k보다 작다면 false
• 문자 빈도수가 홀수개인 문자갯수가 k보다 많으면 false
• 그 외는 모두 true

bool canConstruct(char * s, int k){
    int table[26] = {0};
    int ssize = strlen(s);
    int oddcnt = 0;
    
    if (ssize < k)
        return false;
    for (int i  = 0; i < ssize; i++)
        table[s[i] - 'a']++;
    for (int i  = 0; i < 26; i++) {
        if (table[i] % 2 != 0)
            oddcnt++;
        if (oddcnt > k)
            return false;
    }
    return true;
}