Can Make Palindrome from Substring

Intuition

Solution

class Solution:
    def canMakePaliQueries(self, s: str, queries: List[List[int]]) -> List[bool]:
        counts = {c: ([0] * (len(s) + 1)) for c in string.ascii_lowercase}
        for i, c in enumerate(s):
            for letter in string.ascii_lowercase:
                if letter == c:
                    counts[letter][i + 1] = counts[letter][i] + 1
                else:
                    counts[letter][i + 1] = counts[letter][i]

        ans = []
        for lo, hi, change in queries:
            odd = 0
            for letter in string.ascii_lowercase:
                if (counts[letter][hi + 1] - counts[letter][lo]) % 2 == 1:
                    odd += 1
            if (hi - lo) % 2 == 0:
                odd -= 1
            ans.append(2 * change >= odd)
        return ans