Can Make Palindrome From Substring - Leetcode Solution

Problem:

Given a string s, we make queries on substrings of s.

For each query queries[i] = [left, right, k], we may rearrange the substring s[left], ..., s[right], and then choose up to k 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 an 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 for example s[left..right] = "aaa", and k = 2, we can only replace two of the letters. Also, note that the initial string s is never modified by any query.

Solution:

To solve the problem efficiently, we can use the prefix sum and hashing technique.

1. First of all, we need to calculate the prefix sum of the given string s. Here, the prefix sum represents the frequencies of each character from 0 to i in string s. For example, prefix sum[i]['a'] represents the frequency of 'a' from 0 to i in string s.

2. We also need to calculate the hash value of all substrings of s. Here, the hash value represents the combined result of all characters in a substring. We can use the Rabin-Karp algorithm for hashing.

3. Now, for each query, we need to check if the given substring can be made a palindrome or not. To perform this check, we can compare the frequency of each character in the given substring with its respective frequency in the remaining string. If the difference is less than or equal to k (i.e., the number of characters that are allowed to be replaced), we can make the substring palindrome. Otherwise, we cannot make it a palindrome.

4. To compare the frequency of each character efficiently, we can use the prefix sum that we calculated in step 1. We can subtract the prefix sum of the right end of the substring from the prefix sum of the left end of the substring to get the frequencies of all characters in that substring.

5. Finally, we can use the hash value of the substring that we calculated in step 2 to check if it's a palindrome or not. We can reverse the substring and compare its hash value with the original hash value. If they are equal, the substring is a palindrome.

The time complexity of the above solution is O(n^2), where n is the length of the given string s. However, we can optimize it using dynamic programming to calculate the prefix sum in O(n) time and hashing in O(n^2) time. The overall time complexity of the optimized solution would be O(n^2).

1