Can Make Palindrome from Substring

Problem Description

You are given a string s and an array queries where queries[i] = [left_i, right_i, k_i]. We may rearrange the substring s[left_i...right_i] for each query and then choose up to k_i of them to replace with any lowercase English letter. If the substring is possible to be a palindrome string after the operations above, the result of the query is true. Otherwise, the result is false. Return a boolean array answer where answer[i] is the result of the i-th query queries[i].

Key Insights

• A palindrome can have at most one character with an odd frequency (in the case of odd-length palindromes).
• Count character frequencies in the substring and determine how many characters have odd occurrences.
• The number of characters that must be replaced to form a palindrome can be calculated based on the odd frequency counts.
• The result for each query depends on whether the number of required replacements is less than or equal to k_i.

Space and Time Complexity

Time Complexity: O(n + q * m), where n is the length of the string, q is the number of queries, and m is the average length of the substring in queries.
Space Complexity: O(1) for character frequency counts (fixed size for lowercase letters).

Solution

To solve the problem, we will:

1. Iterate through each query and extract the substring.
2. Count the frequency of each character in the substring.
3. Count how many characters have an odd frequency.
4. Compute how many replacements are needed to make the substring a palindrome using the odd character counts.
5. Compare the required replacements to k_i to determine the result for each query.

Code Solutions