[lufei]_1177. Construct palindrome string detection

1177. Build palindrome string detection

The title

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

Each time the substring to be checked can be represented as queries[I] = [left, right, k]. We can rearrange the substring s[left]… , s[right], and replace up to k of them with any lowercase letter.

The result is true if the substring can be turned into a palindrome string during the above detection, false otherwise.

Return answer array answer[], where answer[I] is the detection result of the ith substring to be checked.

Note: When substituting, 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 of the letters. (Also, none of the checks will modify the original string s, so each check can be considered independent.)

The sample

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. Queries [1] : Substring = "BC", not palindrome. Queries [2] : substring = "abcd", replace only 1 character is not palindrome string. Queries [3] : Substring = "abCD", can be changed into palindrome "abba". You can also change it to "baab", reorder it to "bacd", and then replace "CD" with "ab". Queries [4] : Substring = "abcda", can be changed into palindrome "abCBA".Copy the code

prompt

• 
  $1 <= s.length, queries.length <= 10^5$
• 
  $0 <= queries[i][0] <= queries[i][1] < s.length$
• 
  $0 <= queries[i][2] <= s.length$
• SSS contains only lowercase letters

Answer key

Prefix and + state compression

When the string length and detection array length reach 105 10^5105, the algorithm complexity is lower than O(n2)O(n^2)O(n2).

As prompted, only lowercase letters in S can be placed in an array of length 26. Get a string number prefix array list by enumerating s; List [I] = the number of occurrences of 26 letters before the current string;

When enumerating arrays, check left and right in the array queries[I] = [left, right, k] to find the number of left and right letters in the list array. The number of the 26 English letters in [left,right] can be obtained by subtracting the two

Check whether the interval [left,right] can form a palindrome to save the result

Return an array of results

var canMakePaliQueries = function (s, queries) {
  const path = Array(26).fill(0)
  const list = [[...path]]
  const len = s.length
  for (let i = 0; i < len; i++) {
    const idx = s[i].charCodeAt() - 'a'.charCodeAt()
    path[idx]++
    list.push([...path])
  }
  let result = []
  for (let i = 0; i < queries.length; i++) {
    const [left, right, k] = queries[i]
    const l = list[left]
    const r = list[right + 1]
    let count = 0
    for (let j = 0; j < 26; j++) {
      const t = r[j] - l[j]
      if (t % 2= = =1) count++
    }

    result[i] = k >= (count - 1) / 2
  }
  return result
}
Copy the code

conclusion

The author level is limited, if there is insufficient welcome to correct; Any comments and suggestions are welcome in the comments section