2983. Palindrome Rearrangement Queries

Description

You are given a 0-indexed string s having an even length n.

You are also given a 0-indexed 2D integer array, queries, where queries[i] = [ai, bi, ci, di].

For each query i, you are allowed to perform the following operations:

• Rearrange the characters within the substring s[ai:bi], where 0 <= ai <= bi < n / 2.
• Rearrange the characters within the substring s[ci:di], where n / 2 <= ci <= di < n.

For each query, your task is to determine whether it is possible to make s a palindrome by performing the operations.

Each query is answered independently of the others.

Return a 0-indexed array answer, where answer[i] == true if it is possible to make s a palindrome by performing operations specified by the ith query, and false otherwise.

• A substring is a contiguous sequence of characters within a string.
• s[x:y] represents the substring consisting of characters from the index x to index y in s, both inclusive.

 

Example 1:

Input: s = "abcabc", queries = [[1,1,3,5],[0,2,5,5]]
Output: [true,true]
Explanation: In this example, there are two queries:
In the first query:
- a0 = 1, b0 = 1, c0 = 3, d0 = 5.
- So, you are allowed to rearrange s[1:1] => abcabc and s[3:5] => abcabc.
- To make s a palindrome, s[3:5] can be rearranged to become => abccba.
- Now, s is a palindrome. So, answer[0] = true.
In the second query:
- a1 = 0, b1 = 2, c1 = 5, d1 = 5.
- So, you are allowed to rearrange s[0:2] => abcabc and s[5:5] => abcabc.
- To make s a palindrome, s[0:2] can be rearranged to become => cbaabc.
- Now, s is a palindrome. So, answer[1] = true.

Example 2:

Input: s = "abbcdecbba", queries = [[0,2,7,9]]
Output: [false]
Explanation: In this example, there is only one query.
a0 = 0, b0 = 2, c0 = 7, d0 = 9.
So, you are allowed to rearrange s[0:2] => abbcdecbba and s[7:9] => abbcdecbba.
It is not possible to make s a palindrome by rearranging these substrings because s[3:6] is not a palindrome.
So, answer[0] = false.

Example 3:

Input: s = "acbcab", queries = [[1,2,4,5]]
Output: [true]
Explanation: In this example, there is only one query.
a0 = 1, b0 = 2, c0 = 4, d0 = 5.
So, you are allowed to rearrange s[1:2] => acbcab and s[4:5] => acbcab.
To make s a palindrome s[1:2] can be rearranged to become abccab.
Then, s[4:5] can be rearranged to become abccba.
Now, s is a palindrome. So, answer[0] = true.

 

Constraints:

• 2 <= n == s.length <= 105
• 1 <= queries.length <= 105
• queries[i].length == 4
• ai == queries[i][0], bi == queries[i][1]
• ci == queries[i][2], di == queries[i][3]
• 0 <= ai <= bi < n / 2
• n / 2 <= ci <= di < n
• n is even.
• s consists of only lowercase English letters.

 

Solutions

Solution: Prefix Sum

• Time complexity: O(n)
• Space complexity: O(n)

 

JavaScript

/**
 * @param {string} s
 * @param {number[][]} queries
 * @return {boolean[]}
 */
const canMakePalindromeQueries = function (s, queries) {
  const n = s.length;
  const m = n / 2;
  const leftStr = s.slice(0, Math.max(0, m));
  const rightRevStr = s.slice(Math.max(0, m)).split('').toReversed().join('');
  const pre1 = Array.from({ length: m + 1 }, () => new Array(26).fill(0));
  const pre2 = Array.from({ length: m + 1 }, () => new Array(26).fill(0));
  const diff = new Array(m + 1).fill(0);

  for (let i = 1; i <= m; i++) {
    for (let j = 0; j < 26; j++) {
      pre1[i][j] = pre1[i - 1][j];
      pre2[i][j] = pre2[i - 1][j];
    }
    pre1[i][leftStr.charCodeAt(i - 1) - 97]++;
    pre2[i][rightRevStr.charCodeAt(i - 1) - 97]++;
    diff[i] = diff[i - 1] + (leftStr[i - 1] === rightRevStr[i - 1] ? 0 : 1);
  }

  function check(a, b, c, d) {
    if (diff[a] > 0 || diff[m] - diff[Math.max(b, d) + 1] > 0) {
      return false;
    }

    if (d <= b) {
      const cnt1 = count(pre1, a, b);
      const cnt2 = count(pre2, a, b);
      return cnt1.every((val, i) => val === cnt2[i]);
    }

    if (b < c) {
      if (diff[c] - diff[b + 1] > 0) return false;

      const cnt1_ab = count(pre1, a, b);
      const cnt2_ab = count(pre2, a, b);
      const cnt1_cd = count(pre1, c, d);
      const cnt2_cd = count(pre2, c, d);

      return cnt1_ab.every((val, i) => val === cnt2_ab[i]) && cnt1_cd.every((val, i) => val === cnt2_cd[i]);
    }

    if (c <= b && b < d) {
      const cnt1 = sub(count(pre1, a, b), count(pre2, a, c - 1));
      const cnt2 = sub(count(pre2, c, d), count(pre1, b + 1, d));

      return cnt1.every((val, i) => val >= 0 && cnt2[i] >= 0 && val === cnt2[i]);
    }

    return false;
  }

  return queries.map(([a, b, c, d]) => {
    const c2 = n - 1 - d;
    const d2 = n - 1 - c;

    if (a <= c2) {
      return check(a, b, c2, d2);
    } else {
      return check(c2, d2, a, b);
    }
  });
};

function count(pre, l, r) {
  const res = new Array(26).fill(0);

  if (l > r) return res;
  for (let i = 0; i < 26; i++) {
    res[i] = pre[r + 1][i] - pre[l][i];
  }
  return res;
}

function sub(a, b) {
  const res = new Array(26).fill(0);

  for (let i = 0; i < 26; i++) {
    res[i] = a[i] - b[i];
  }
  return res;
}