**Short Palindrome

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

문제

주어진 문자열에서 4개의 문자를 뽑아 회문을 만든다고 했을 때, 나오는 경우의 수를 반환하라.
이 때, 각 문자 a, b, c, d의 인덱스 순서는 0 <= a < b < c < d < |s| 이다.

1. 나의 풀이

회문 관련된 문제는 감을 아직 잡기가 어려운 것 같다. 좀 더 비슷한 유형의 문제들을 접해야 겠다는 생각이 들었다.

2. 다른사람의 풀이

아래 X는 outer를 뜻하고 Y는 inner를 뜻한다.

솔직히 아래 로직을 다 해석하진 못했다. 시간적 여유가 생긴다면 마저 해석해 보기로 했다.

function shortPalindrome(s) {
    // Write your code here
    const seenCount = Array(26).fill(0);
    const count = seenCount.slice();
    const xyCount = Array(26 * 26).fill(0);
    const m = 1000000007;

    let totalCount = 0;

    for (const k of s) {
      	// 현재 문자
        const X = k.charCodeAt(0) - 'a'.charCodeAt(0);
        let XY = X;

        totalCount = (totalCount + count[X]) % m;

        for (let i = 0; i < 26; i++) {
            count[i] = (count[i] + xyCount[XY]) % m;
            xyCount[XY] = (xyCount[XY] + seenCount[i]) % m;
            XY += 26;
        }

      	// X가 나타난 횟수 증가
        seenCount[X]++;
    }
    return totalCount;
}