Can Make Palindrome from Substring
You are given a string s and an array queries where queries[i] = [lefti, righti, ki].
For each query, you may:
- Rearrange the substring
s[lefti...righti]. - Choose up to
kiletters in that substring and replace each chosen letter with any lowercase English letter.
If the substring can become a palindrome after these operations, 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].
Note that each letter is counted individually for replacement, so if s[lefti...righti] = "aaa" and ki = 2, you can only replace two of the letters. Also, no query modifies the initial string s.
Example 1
Input
s = "abcda", queries = [[3,3,0],[1,2,0],[0,3,1],[0,3,2],[0,4,1]]Output
[true,false,false,true,true]The query results are true for substrings that are already palindromes or can be rearranged and changed within the allowed replacements, and false otherwise.
Example 2
Input
s = "lyb", queries = [[0,1,0],[2,2,1]]Output
[false,true]The substring "ly" cannot be made a palindrome with 0 replacements, while the single-character substring "b" is already a palindrome.
Constraints
- 1 <= s.length, queries.length <= 10^5
- 0 <= lefti <= righti < s.length
- 0 <= ki <= s.length
- s consists of lowercase English letters.