Abstract: This topic needs to fully explore the nature of palindrome, focus on understanding the keyword in the topic of “rearrangement”, and fully understand the characteristics of “xor” operation.

Answer key | “power button” 1177: building a palindrome bunch of detection

Given a string s, you are asked to check the substring of S.

Query [I] = [left, right, k]. We can rearrange the substring s[left],… , s[right], and select up to K items to replace with any lowercase English letter.

The result is true if the substring can be changed to a palindromic string during the above detection; otherwise, the result is false.

Return answer[], where answer[I] is the test result of the i-th substring to be checked.

Note: During substitution, each letter in the substring must be counted as a separate item, that is, if s[left.. Right] = “aaa” and k = 2, we can only replace two letters. In addition, the original string s is not modified by any of the checks, so each check can be considered independent.

Example:

Input: s = "abcda", the queries = [,3,0 [3], [0] 1,,3,1 [0], [31] 0,,4,1 [0]] output: [true, false, false, true, true] : the queries [0] : Substring = "d", palindrome. Query [1] : substring = "BC", not palindrome. [2] : substring = "abcd"; replace only one character. Query [3] : substring = "abcd", which can be changed to "abba". You can also change it to "baab", reorder it to "bacd", and then replace "CD" with "ab". Query [4] : substring = "abcda", which can be changed to "abcba".Copy the code

Tip:

• 
  $1 \le s.length, queries.length \le 10^5$
• 
  $0 \le queries[i][0] \le queries[i][1] < s.length$
• 
  $0 \le queries[i][2] \le s.length$
• sOnly lowercase letters are included in the script

Knowledge:

• The sum of the xOR prefix and makes up the information in the interval;
• The state compression technique is also used.

Thinking analysis:

• Replace the mostkAfter the time can also adjust the position of lowercase English letters, palindrome;
• The brute force solution is to enumerate all the substringss[i..j]The number of occurrence of 26 lowercase English letters in Chinese;
• The question doesn’t really care how it is arranged, so we only need to care about the number of occurrences of characters in each query.
• whilequeryRepresents the continuous subinterval of the string, so we need to know the number of characters in the subinterval of the string;
• Focus onIn palindrome, if a character occurs an even number of times, it can be placed in a symmetric position of the string, and we can ignore the even number of occurrences. In other words,kThe second chance should first satisfy an odd number of occurrences of the string and should only replace single characters that do not form a pair;
• To understand information in continuous subintervals, it’s easy to think of the prefix sum.

Reference code:

import java.util.ArrayList;
import java.util.List;

public class Solution {

    public List<Boolean> canMakePaliQueries(String s, int[][] queries) {
        int len = s.length();
        char[] charArray = s.toCharArray();

        // Step 1: Calculate the prefix xOR sum
        int[] preSum = new int[len + 1];
        preSum[0] = 0;
        for (int i = 0; i < len; i++) {
            preSum[i + 1] = preSum[i] ^ (1 << (charArray[i] - 'a'));
        }
        // Step 2: Calculate the result based on the prefix xor and
        List<Boolean> res = new ArrayList<>();
        for (int[] query : queries) {
            // Note the difference or subtraction between the interval and the sum
            res.add(Integer.bitCount(preSum[query[0]] ^ preSum[query[1] + 1) /2 <= query[2]);
        }
        returnres; }}Copy the code

Description:

preSum[query[0]] ^ preSum[query[1] + 1]
Copy the code

The sum of the xor prefix is the sum of the intervals. This is because xor is characterized by non-carry addition. The number of digits after the same xor is 000.

Correlation problem:

191. Number of bits of 1

Reference code:

public class Solution {
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
        int res = 0;
        while(n ! =0) {
            n &= n - 1;
            res++;
        }
        returnres; }}Copy the code