[LeetCode] 1400. Construct K Palindrome Strings

1400. Construct K Palindrome Strings

링크

풀이

s라는 string과 k라는 integer가 입력으로 주어진다.
s가 k개의 펠린드롬으로 나누어질 수 있는지에 대해 물어보는 문제이다.
펠린드롬의 조건을 생각하면 중간을 기준으로 대칭이어야 한다.
이에 따라서 짝수 개수의 알파벳 + k보다 작거나 같은 홀수 개수의 알파벳이 필요하다.
k보다 작거나 같아야 하는 이유는 짝수 개수의 알파벳을 통해서 펠린드롬 문자열을 만들 수 있는 경우의 수가 k개이기 때문이다.

말로 보면 어려운데, 예시를 보면 쉽다.

Input: s = "true", k = 4
Output: true
Explanation: The only possible solution is to put each character in a separate string.

위의 예시를 보면 true는 홀수 개수의 알파벳이 4개고 k가 4이기에 t,r,u,e로 문제의 조건을 만족한다.

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"

위의 예시에서는 홀수 개수의 알파벳이 b 하나 이기에, 어떤 문자열을 만들어도 b를 끼워넣을 수 있으므로 문제의 조건을 만족한다.

마지막으로, s는 k보다 항상 크거나 같아야 펠린드롬을 만들어낼 수 있다.
'abc'라는 문자열을 주고 10개의 펠린드롬을 만들라고 지시하면 만들 수 있는가?
알파벳 개수가 애초에 3개밖에 안되서 만족할 수 없는 조건이다.

코드

/**
 * @param {string} s
 * @param {number} k
 * @return {boolean}
 */

var getOrDefault = function(map, alphabet) {
    if(map.get(alphabet)) {
        return map.get(alphabet);
    }
    return 0;
}

var canConstruct = function(s, k) {
    const alphabets = new Map();
    for(let i = 0 ; i < s.length ; i++) {
        alphabets.set(s[i], getOrDefault(alphabets, s[i])+1);
    }

    let oddCount = 0;

    for(const entry of alphabets) {
        if(entry[1] % 2 === 1) oddCount++;
    }

    if (oddCount <= k && s.length >= k) return true;

    return false;
};