[LeetCode] 1915. Number of Wonderful Substrings

https://leetcode.com/problems/number-of-wonderful-substrings/description/

leetcode - Number of Wonderful Substrings

문제 유형 : 비트마스킹, 비트 조작

문제 난이도 : Medium

 

 

문제

A wonderful string is a string where at most one letter appears an odd number of times.

• For example, "ccjjc" and "abab" are wonderful, but "ab" is not.

Given a string word that consists of the first ten lowercase English letters ('a' through 'j'), return the number of wonderful non-empty substrings in word. If the same substring appears multiple times in word, then count each occurrence separately.

A substring is a contiguous sequence of characters in a string.

 

훌륭한 문자열은 홀수개의 문자가 최대 1번만 나오는 문자열을 말한다.

예를 들어, "ccjjc"와 "abab"는 훌륭하지만, "ab"는 그렇지 않다.

 

문자열 word가 a~j의 범위의 문자들로 구성된다. word의 훌륭한 부문자열의 개수를 구하시오.

같은 문자열이라도 인덱스가 다르면, 다른 문자열로 칩니다.

 

풀이

개수를 셀 변수, 전위부의 xor값을 담을 변수 prefixXor, 전위부의 xor의 개수를 담는 1024짜리 배열 count를 만든다.

문자열의 문자를 순서대로 읽으면서, 다음을 진행한다:

 우선, 문자의 번호를 알아낸다.('a'를 0번으로 잡고, 'j'를 9번으로 잡는다.)

 이번에 읽은 문자와 이전 전위부 xor값과 xor연산을 한다.

 개수 변수에는 count[prefixXOR]을 누적시킨다.

 그리고 prefixXOR의 이전 뒤집을 수 있는 비트들에 대해 count에 저장된 만큼 값을 누적시킨다.

 count[prefixXOR]의 값을 1 늘린다.

 

최종적으로 개수를 반환한다.

 

코드

C++

class Solution {
public:
    long long wonderfulSubstrings(string word) {
        vector<long long> count(1024, 0);
        long long res = 0;
        int prefixXor = 0;
        count[prefixXor] = 1;

        for(auto ch : word) {
            int charIndex = ch - 'a';
            prefixXor ^= 1 << charIndex;
            res += count[prefixXor];
            for(int i = 0; i < 10; i++) {
                res += count[prefixXor ^ (1 << i)];
            }
            count[prefixXor]++;
        }

        return res;
    }
};