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