thảo luận Leetcode mỗi ngày

public class Solution
{
    public long WonderfulSubstrings(string word)
    {
        long[] count = new long[1024];
        count[0] = 1;

        int state = 0;
        long result = 0;

        for (int i = 0; i < word.Length; i++)
        {
            state ^= 1 << (word[i] - 'a');
            
            result += count[state];
            for (char odd = 'a'; odd <= 'j'; odd++)
            {
                int oddState = state ^ (1 << odd - 'a');
                result += count[oddState];
            }

            count[state]++;
        }

        return result;
    }
}

class Solution:
    def wonderfulSubstrings(self, word: str) -> int:
        # For each prefix of the string, check which characters are of even frequency and which are not and represent it by a bitmask
        ## ten lowercase English letters => bitmask in range (0, 1024)
        bitmask_freq_table = [0] * 1024

        cur_bitmask = 0

        bitmask_freq_table[cur_bitmask] += 1
        for char in word:
            cur_bitmask ^= 1 << (ord(char) - ord('a'))
            bitmask_freq_table[cur_bitmask] += 1

        # Find the other prefixes whose masks differs from the current prefix mask by at most one bit
        count = 0

        for mash1 in range (0, 1024):
            count += bitmask_freq_table[mash1] * (bitmask_freq_table[mash1] - 1) // 2
            for bit in range (10):
                mash2 = mash1 ^ (1 << bit)
                if mash1 < mash2:
                    count += bitmask_freq_table[mash1] * bitmask_freq_table[mash2]

        return count

const charCodeOfA = 'a'.charCodeAt(0);
Object.defineProperty(String.prototype, 'code', {
    get() {
        return this.charCodeAt(0) - charCodeOfA;
    }
});
var wonderfulSubstrings = function (word) {
    const ctr = [1];
    let i = 0, ans = 0;
    for (const ch of word) {
        i ^= 1 << ch.code;
        ctr[i] ??= 0;
        ans += ctr[i];
        for (let b = 1; b < (1 << 10); b <<= 1) {
            ans += ctr[i ^ b] ?? 0;
        }
        ctr[i]++;
    }
    return ans;
};

class Solution:
    def wonderfulSubstrings(self, word: str) -> int:
        ret, num = 0, 0
        d = defaultdict(int)
        d[num] += 1        
        for w in word:
            num ^= 1 << (ord(w) - ord('a'))
            ret += sum(d[num^x] for x in [0,1,2,4,8,16,32,64,128,256,512])
            d[num] += 1
        return ret

public long wonderfulSubstrings(String word) {
        int wordLength = word.length();
        int[] frequency = new int['j' - 'a' + 1];
        long wordCount = 0;
        int oddCount = 0;

        for (int i = 0; i < wordLength; i++) {
            for (int j = i; j < wordLength; j++) {
                int charIdx = word.charAt(j) - 'a';
                frequency[charIdx]++;

                int f = frequency[charIdx];

                if (f % 2 > 0) {
                    oddCount++;
                } else {
                    oddCount--;
                }

                if (oddCount > 1) {
                    continue;
                } else {
                    wordCount++;
                }

            }

            oddCount = 0;
            Arrays.fill(frequency, 0);
        }

        return wordCount;
    }