[Leetcode] 1930. Unique Length-3 Palindromic Subsequences

주어진 문자열에서 길이가 3인 고유한 회문(palindrome)을 찾아내는 문제. 회문을 이루는 알파벳들이 붙어있을 필요는 없다. 문자열은 영단어 소문자로만 구성되어 있다는 전제조건이 있다.

문자열을 한 번 돌면서 문자열을 구성하는 알파벳들의 처음과 끝을 찾는다. 이후 처음과 마지막 문자열 사이의 값들중에서 유니크한 값을 찾아내기만 하면 된다. 알파벳마다 한번씩 돌게 되므로 매 반복마다 찾아낸 고유한 값이 충돌할 리는 없다. 반복시마다 Set을 하나 만들지만 반복을 도는 것 보다는 낫다고 생각해서 돌려봤는데 무난하게 통과.

function countPalindromicSubsequence(s: string): number {
    const charMap = new Map()

    for (let i = 0; i < s.length; i++ ) {
        const char = s[i]

        if (charMap.has(char)) {
            charMap.get(char).last = i
        } else {
            charMap.set(char, { first: i, last: i })
        }
    }

    let size = 0;

    for (const [char, { first, last }] of charMap.entries()) {
        if (last - first < 2) {
            continue;
        }

        const subSet = new Set(s.slice(first + 1, last).split(''))
        size += subSet.size;
    }

    return size;
};