[LeetCode] 1400. Construct K Palindrome Strings

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

leetcode - Construct K Palindrome Strings

문제 유형: 문자열 처리, 팰린드롬

문제 난이도: Medium

 

문제

Given a string s and an integer k, return true if you can use all the characters in s to construct k palindrome strings or false otherwise.

 

문자열 s와 정수 k가 주어집니다. 만약 s의 글자들로 k개의 팰린드롬 문자열로 만들 수 있으면 true를 아니면 false를 반환하시오.

 

풀이

꽤 트리키해 보일 수 있지만, 문제를 간단하게 만들 수 있다.

생각해보면, 팰린드롬을 구성하기 위해서는 길이가 홀수인경우의 가운데를 제외하면 짝수 쌍이 덮고 있는 꼴로 존재한다.

즉, 생성되는 모든 페어들에 대해서는 베재하고 생각해도 좋다.

실제로 중요한 것은, 홀로 남은 글자들이 가운데를 맡을 수 있는지이다. 만약 홀로 남은 글자들이 k보다 크다면, 불가능해진다.

 

우선, 문자열을 순회하여 글자별 빈도를 저장한다.

변수 x에 글자별 빈도 MOD 2를 누적한다.

x가 k이하인 경우 k개의 팰린드롬을 만들 수 있다.

그러나, x가 k보다 크면 불가능하다.

 

 

코드

C++

class Solution {
public:
    bool canConstruct(string s, int k) {
        if(s.size() < k) return false;
        vector<int> freq(26, 0);
        for(char ch : s) {
            freq[ch-'a']++;
        }
        int x = 0;
        for(int  i = 0; i < 26; ++i) {
            x += freq[i]%2;
        }
        return x <= k;
    }
};