Problem statement

https://leetcode.com/problems/can-make-palindrome-from-substring/

Solution

What we need to find for each query is number of odd frequencies. We can keep cumulative frequencies of values, where we keep information about odd and even frequency. Then for each frequency we need to calcualte number of 1 bits.

Complexity

It is O(n * 32) for time and O(n) for space. To optimize we can use faster way to check number of bits.

Code

class Solution:
    def canMakePaliQueries(self, s, q):
        acc, n = [0], len(s)
        for x in s:
            acc += [acc[-1] ^ (1<<(ord(x) - 97))]
        ans = []
        for x, y, k in q:
            ans += [bin((acc[x]^acc[y+1])).count("1") <= 2*k + 1]
            
        return ans