**Maximum Palindromes

사이트: HackerRank
난이도: 미디움
분류: String

문제

어느 문자열과 특정 구간값이 주어졌을 때 해당 구간안에 존재하는 가장 긴 길이의 palindromes(회문)의 개수를 반환해라.

1. 나의 풀이

어찌저찌 initialize 함수에서 구간 합을 구해야 하고, 해당 구간합을 이용해 팩토리얼 계산하는 것 까지는 진행했었다. 다만 마지막에 문자의 중복인 경우의 수를 계산하는 것이 어려워서 시간을 많이 소모한 것 같다.
결국 혼자서는 다 해결하지 못하고 테스트 케이스를 16/32 정도만 통과할 수 있었다.

let partial = [];
function initialize(s) {
    // This function is called once before all queries.
    const str = Array.from(s);

    // partial sum?
    for (let i = 0; i < str.length; i++) {
        partial[i] = { ...(partial[i - 1] || {}) };
        partial[i][str[i]] = (partial[i][str[i]] || 0) + 1;
    }
}

function answerQuery(l, r) {
    // Return the answer for this query modulo 1000000007.
    const lp = partial[l - 2] || {};
    const rp = partial[r - 1];
    
    let frontCount = 0;
    let oddCount = 0;
    let uniqueCount = 0;

    for (const [key, value] of Object.entries(rp)) {
        const count = value - (lp[key] || 0);

        if (count === 0) {
            continue;
        }
        
        if (count % 2 === 1) {
            oddCount++;
        }
        
        frontCount += Math.floor(count / 2);
        uniqueCount++;
    }
    
    let result = 1;
    for (let i = frontCount; i > 0; i--) {
      	// 해당 연산의 처리가 어려웠다 ㅠㅠ
        result *= i > uniqueCount ? uniqueCount : i;
    }

    return Math.max(oddCount, 1) * result;
}

2. 다른사람의 풀이

hackerRank에 올라온 java 코드를 변환해서 써봤는데, 뭔가 문제가 있는지 20/32밖에 통과하지 못했다. 페르마의 소정리를 사용해서 modulo 연산을 해야 하는 문제이다.

해당 문제는 진짜 안풀어보면 잘 모를거 같다. 솔직히 첨부한 블로그 글의 내용만 봐서는 해당 알고리즘 문제를 풀기가 어려웠다. 일단은 넘어거고 시간적 여유가 생긴다면 더 진행하도록 하겠다.

const R = 26;
const MOD = 1000000007;
let n;
let csum;
let fac;
let ifac;

function inv(v, m) {
    return (extendedGCD(v, m)[0] % m + m) % m;
}

function extendedGCD(x, y) {
    const ans = [];
    if (y == 0) {
        ans[0] = 1;
        ans[1] = 0;
        ans[2] = x;
        return ans;
    }
    
    let q = Math.floor(x / y);
    let r = x % y;
    let t = extendedGCD(y, r);
    ans[0] = t[1];
    ans[2] = t[2];
    ans[1] = t[0] - ans[0] * q;
    return ans;
}

function initialize(s) {
    // This function is called once before all queries.
    n = s.length;
    csum = Array.from(new Array(R), () => new Array(n + 1));

    for (let i = 1; i <= n; i++) {
        const id = s.charAt(i - 1).charCodeAt() - 'a'.charCodeAt();
        for (let j = 0; j < R; j++) {
            csum[j][i] = (csum[j][i - 1] || 0);
            csum[id][i] = (csum[id][i - 1] || 0) + 1;
        }
    }

    fac = new Array(n+1);
    ifac = new Array(n+1);
    fac[0] = 1;
    ifac[0] = 1;

    for (let i = 1; i <= n; i++) {
        fac[i] = fac[i - 1] * i % MOD;
        ifac[i] = ifac[i - 1] * inv(i, MOD) % MOD;
    }
}

function answerQuery(l, r) {
    // Return the answer for this query modulo 1000000007.
    let nmid = 0;
    let nside = 0;
    let ans = 1;

    for (let i = 0; i < R; i++) {
        let cnt = (csum[i][r] || 0) - (csum[i][l-1] || 0);
        let left = Math.floor(cnt / 2);
        nside += left;
        ans = ans * ifac[left] % MOD;
        if (cnt % 2 == 1) {
            nmid++;
        }
    }

    ans = ans * fac[nside] % MOD;
    if (nmid > 1) {
        ans = ans * nmid % MOD;
    }
    return ans;
}