Leetcode 1281 Solution

This article provides solution to leetcode question 1281 (can-make-palindrome-from-substring)
Categories:
Tags:
Access this page by simply typing in "lcs 1281" in your browser address bar if you have bunnylol configured.

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

Solution

class Solution:
    def canMakePaliQueries(self, s: str, queries: List[List[int]]) -> List[bool]:
        cnts = [[0 for _ in range(26)] for _ in range(len(s) + 1)]

        for i, ch in enumerate(s):
            cnts[i + 1] = list(cnts[i])
            cnts[i + 1][ord(ch) - ord('a')] += 1

        ans = []
        for start, end, k in queries:
            start_cnts = cnts[start]
            end_cnts = cnts[end + 1]

            odd_cnt = 0
            for i in range(26):
                if (end_cnts[i] - start_cnts[i]) % 2 == 1:
                    odd_cnt += 1

            ans.append(k >= odd_cnt // 2)

        return ans