LC-1177. Build palindrome detection (XOR prefix and + state compression)

Reference: Step by step optimization! From prefix sums to prefix xor sums (attached sheet!)

https://leetcode.cn/problems/can-make-palindrome-from-substring/solution/yi-bu-bu-you-hua-cong-qian-zhui-he-dao-q-yh5p/

1177. Construct palindrome detection

Moderate 113

Given a string s, please check the substring of s.

For each detection, the substring to be checked can be expressed as queries[i] = [left, right, k]. We can rearrange the substrings s[left], ..., s[right] and choose from them at most k item is replaced with any lowercase English letter.

If in the above detection process, the substring can be changed into a palindrome string, then the detection result is true, otherwise the result is false.

Return the answer array answer[], where answer[i] is the i substring queries[i] to be checked code> detection results.

NOTE: When substituting, each letter in the substring must be counted as a independent item, that is, if s[left..right] = "aaa" and k = 2, we can only replace two letters in it. (In addition, any detection will not modify the original string s, each detection can be considered independent)

Example:

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]
explain:
queries[0] : substring = "d", palindrome.
queries[1] : substring = "bc", not a palindrome.
queries[2] : substring = "abcd", only replacing 1 character will not become a palindrome.
queries[3] : substring = "abcd", which can be turned into palindrome "abba". It can also be changed to "baab", by first reordering to become "bacd", and then replacing "cd" with "ab".
queries[4] : substring = "abcda", which can be changed into palindrome "abcba".

Tip:

  • 1 <= s.length, queries.length <= 10^5
  • 0 <= queries[i][0] <= queries[i][1] < s.length
  • 0 <= queries[i][2] <= s.length
  • Only lowercase English letters in s

Violence (timeout)

For each query, count the number of occurrences of characters, and then count the number of odd characters for answer comparison (timeout)

class Solution {<!-- -->
    public List<Boolean> canMakePaliQueries(String s, int[][] queries) {<!-- -->
        List<Boolean> ans = new ArrayList<>();
        char[] arr = s.toCharArray();
        for (int[] q : queries) {<!-- -->
            int left = q[0], right = q[1], k = q[2];
            if(left == right){<!-- -->
                ans. add(true);
                continue;
            }
            int[] cnt = new int[26];
            int diff = 0;
            for (int i = left; i <= right; i ++ ) {<!-- -->
                cnt[arr[i] - 'a'] + = 1;
                if (cnt[arr[i] - 'a'] == 2) {<!-- -->
                    diff -= 1;
                    cnt[arr[i] - 'a'] = 0;
                } else
                    diff += 1;
            }
            if (diff / 2 <= k) // There are a total of diff different characters, you need to modify the diff/2 characters to become a palindrome
                ans. add(true);
            else
                ans. add(false);
        }
        return ans;
    }
}

The last problem to be solved is how to quickly find the number of each letter in the substring?

26 arrays of prefixes and can be created, counting each letter separately. Take the letter a as an example, when calculating the prefix sum, if s[i]=a is regarded as 1, otherwise it is regarded as 0

Prefix sum (before optimization)

https://leetcode.cn/problems/can-make-palindrome-from-substring/solution/yi-bu-bu-you-hua-cong-qian-zhui-he-dao-q-yh5p/

Algorithm (before optimization)

1. How many times each letter appears in the prefix of length i of preprocessing s. For the convenience of subsequent optimization, the two-dimensional array sum of n x 26 is used here to store the prefix sum, where sum[i + 1][j] represents The number of occurrences of the j lowercase letter of the alphabet from s[0] to s[i].

2. For queries[i] , use the prefix sum to calculate the number of occurrences of each letter, count how many letters appear odd times, and set it to m. If m/2 <= k , then answer[i] is true, otherwise false

class Solution {<!-- -->
    public List<Boolean> canMakePaliQueries(String s, int[][] queries) {<!-- -->
        int n = s. length();
        int[][] sum = new int[n + 1][26];
        for(int i = 0; i < n; i ++ ){<!-- -->
            sum[i + 1] = sum[i]. clone();
            sum[i + 1][s.charAt(i) - 'a'] + + ;
        }
        List<Boolean> ans = new ArrayList<Boolean>(queries.length); // pre-allocate space
        for(int[] q : queries){<!-- -->
            int left = q[0], right = q[1], k = q[2];
            int m = 0;
            for(int j = 0; j < 26; j ++ ){<!-- -->
                m + = (sum[right + 1][j] - sum[left][j]) % 2; // odd + 1, even + 0
            }
            ans. add(m / 2 <= k);
        }
        return ans;
    }
}

XOR prefix sum (step by step optimization)

Since we only care about the parity of the number of occurrences of each letter, there is no need to store the number of occurrences of each letter in the prefix sum, only the parity of the number of occurrences of each letter needs to be saved.

For the convenience of calculation, 0 is used to represent an even number of occurrences, and 1 is used to represent an odd number of occurrences.

Note that an odd number can only be obtained by subtracting an even number from an odd number, or subtracting an odd number from an even number. So if the result of the subtraction is not 0 (or the two subtracted numbers are not equal), it means that there has been an odd number of times.

class Solution {<!-- -->
    public List<Boolean> canMakePaliQueries(String s, int[][] queries) {<!-- -->
        int n = s. length();
        int[][] sum = new int[n + 1][26];
        for(int i = 0; i < n; i ++ ){<!-- -->
            sum[i + 1] = sum[i]. clone();
            sum[i + 1][s.charAt(i) - 'a'] + + ;
            sum[i + 1][s.charAt(i) - 'a'] %= 2; // even number is 0
        }
        List<Boolean> ans = new ArrayList<Boolean>(queries.length); // pre-allocate space
        for(int[] q : queries){<!-- -->
            int left = q[0], right = q[1], k = q[2];
            int m = 0;
            for(int j = 0; j < 26; j ++ )
                m + = (sum[right + 1][j] != sum[left][j] ? 1 : 0);
            ans. add(m / 2 <= k);
        }
        return ans;
    }
}

Since the XOR operation satisfies the result of 1 and 0 is 1, and the result of 0 and 0, and 1 and 1 is 0, so the above subtraction can be replaced by XOR.

class Solution {<!-- -->
    public List<Boolean> canMakePaliQueries(String s, int[][] queries) {<!-- -->
        int n = s. length();
        int[][] sum = new int[n + 1][26];
        for(int i = 0; i < n; i ++ ){<!-- -->
            sum[i + 1] = sum[i]. clone();
            sum[i + 1][s.charAt(i) - 'a'] ^= 1; // odd number becomes even number, even number becomes odd number
        }
        List<Boolean> ans = new ArrayList<Boolean>(queries.length); // pre-allocate space
        for(int[] q : queries){<!-- -->
            int left = q[0], right = q[1], k = q[2];
            int m = 0;
            for(int j = 0; j < 26; j ++ )
                m + = sum[right + 1][j] ^ sum[left][j];
            ans. add(m / 2 <= k);
        }
        return ans;
    }
}

XOR prefix and + state compression

Since only 0 and 1 are stored in an array with a length of 26, it can be compressed into a binary number, and the i-th bit of the binary number stores the information of 0 and 1 from low to high.

For example, binary 10010 means an odd number of occurrences of b and e and an even number of occurrences of the remaining letters.

When computing prefix sums (XOR prefix sums to be precise):

  • Modify the parity of the number of occurrences of a, which can be exclusive or binary 1;
  • Modify the parity of the number of occurrences of b, which can be exclusive or binary 10;
  • Modify the parity of the number of occurrences of c, you can XOR binary 100;
  • So on and so forth.

In addition, since XOR can be "calculated in parallel", directly XOR the two binary numbers in the prefix sum to obtain the parity of the number of occurrences of each letter in the substring. Then count the number of 1s in this binary number to get m.

For example, 10010⊕01110=11100, indicating that there are 3 kinds of letters that appear odd times.

class Solution {<!-- -->
    public List<Boolean> canMakePaliQueries(String s, int[][] queries) {<!-- -->
        int n = s. length();
        int[] sum = new int[n + 1];
        for(int i = 0; i < n; i ++ ){<!-- -->
            int bit = 1 << (s. charAt(i) - 'a');
            sum[i + 1] = sum[i] ^ bit; // This bit corresponds to the parity of the letter: odd numbers become even numbers, even numbers become odd numbers
        }
        List<Boolean> ans = new ArrayList<Boolean>(queries.length); // pre-allocate space
        for(int[] q : queries){<!-- -->
            int left = q[0], right = q[1], k = q[2];
            int m = Integer. bitCount(sum[right + 1] ^ sum[left]);
            ans. add(m / 2 <= k);
        }
        return ans;
    }
}

Question: How did you come up with XOR?

Answer: XOR can be regarded as "addition without carry (subtraction)" or "addition (subtraction) in the remainder system modulo 2", so it is often used to solve some problems related to parity.

Similar topic (prefix sum + XOR)

  • 1371. Longest substring containing even number of times each vowel
  • 1542. Find Longest Awesome Substring
  • 1915. Number of the most beautiful substrings, solution

More prefixes and titles:

  • 560. Subarrays Sum K
  • 974. Sum of Subarrays Divisible by K
  • 1590. Make Array Sum Divisible by P
  • 523. Consecutive Subarray Sum
  • 525. Contiguous Arrays
syntaxbug.com © 2021 All Rights Reserved.