#2983

Hard

LeetCode Problem Workspace

Palindrome Rearrangement Queries

Given a string and queries, check if rearranging specified substrings can make the string a palindrome.

Problem Statement

You are given a string s of even length n and a 2D array queries. Each query defines two substrings from the left and right halves of s with the aim of checking if they can be rearranged to form a palindrome. For each query, you need to decide if it's possible to rearrange these substrings to create a valid palindrome.

The key operation involves selecting specified ranges in the left and right halves of the string and checking if the characters can be rearranged into a palindrome. This requires using hash table-based frequency counting for optimal results and efficiently handling multiple queries.

Examples

Example 1

Input: s = "abcabc", queries = [[1,1,3,5],[0,2,5,5]]

Output: [true,true]

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]

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]

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.

Solution Approach

Frequency Count for Substrings

To solve this, the characters of the substrings involved in each query are counted using a hash table. The idea is that a string can form a palindrome if at most one character has an odd frequency. This allows us to check the possibility of forming a palindrome from rearranged substrings.

Efficient Query Handling with Prefix Sums

Using prefix sums allows efficient retrieval of character frequencies for substrings. This helps to reduce the time complexity for each query by allowing the substring frequency calculation to be done in constant time.

Checking Palindrome Condition

For each query, after calculating the frequencies of the characters in the selected substrings, we check if the condition of having at most one odd frequency is satisfied. If it is, the substrings can be rearranged into a palindrome.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity of this problem depends on the approach used for calculating the character frequencies and answering each query. With prefix sums, answering each query can be done in constant time, leading to an overall time complexity of O(n + q), where n is the length of the string and q is the number of queries. Space complexity is O(n) due to the prefix sum and frequency tables.

What Interviewers Usually Probe

Candidate demonstrates the ability to efficiently solve range-based substring problems using hash tables.
The candidate effectively utilizes prefix sums for fast query resolution.
The candidate shows an understanding of palindrome conditions and string manipulation techniques.

Common Pitfalls or Variants

Common pitfalls

Failing to optimize the solution by not using prefix sums for frequency calculations.
Incorrectly checking for palindrome conditions, not accounting for multiple odd frequencies in the substrings.
Not managing large inputs effectively, leading to time complexity issues.

Follow-up variants

Allow for more than two substrings in each query.
Extend the problem to handle queries involving substrings in the same half of the string.
Implement a solution that minimizes the space complexity while still answering queries efficiently.

FAQ

What is the core idea behind solving the Palindrome Rearrangement Queries problem?

The problem relies on efficiently checking if substrings of a string can be rearranged to form a palindrome using character frequency counts and prefix sums.

How can prefix sums improve the performance of this problem?

Prefix sums allow us to calculate the frequency of characters in any substring in constant time, significantly reducing the time complexity of each query.

What is the time complexity of the Palindrome Rearrangement Queries problem?

The time complexity is O(n + q), where n is the length of the string and q is the number of queries, assuming prefix sums are used for efficient query handling.

Can the solution be optimized further?

Yes, optimizing for space or handling more complex queries by using different data structures or algorithms could lead to further improvements.

What is the importance of hash tables in this problem?

Hash tables are crucial for counting character frequencies efficiently, which is the key step in determining whether substrings can be rearranged into a palindrome.

terminal

Solution

Solution 1: Prefix Sum + Case Discussion

Let's denote the length of string $s$ as $n$, then half of the length is $m = \frac{n}{2}$. Next, we divide string $s$ into two equal-length segments, where the second segment is reversed to get string $t$, and the first segment remains as $s$. For each query $[a_i, b_i, c_i, d_i]$, where $c_i$ and $d_i$ need to be transformed to $n - 1 - d_i$ and $n - 1 - c_i$. The problem is transformed into: for each query $[a_i, b_i, c_i, d_i]$, determine whether $s[a_i, b_i]$ and $t[c_i, d_i]$ can be rearranged to make strings $s$ and $t$ equal.

class Solution:
    def canMakePalindromeQueries(self, s: str, queries: List[List[int]]) -> List[bool]:
        def count(pre: List[List[int]], i: int, j: int) -> List[int]:
            return [x - y for x, y in zip(pre[j + 1], pre[i])]

        def sub(cnt1: List[int], cnt2: List[int]) -> List[int]:
            res = []
            for x, y in zip(cnt1, cnt2):
                if x - y < 0:
                    return []
                res.append(x - y)
            return res

        def check(
            pre1: List[List[int]], pre2: List[List[int]], a: int, b: int, c: int, d: int
        ) -> bool:
            if diff[a] > 0 or diff[m] - diff[max(b, d) + 1] > 0:
                return False
            if d <= b:
                return count(pre1, a, b) == count(pre2, a, b)
            if b < c:
                return (
                    diff[c] - diff[b + 1] == 0
                    and count(pre1, a, b) == count(pre2, a, b)
                    and count(pre1, c, d) == count(pre2, c, d)
                )
            cnt1 = sub(count(pre1, a, b), count(pre2, a, c - 1))
            cnt2 = sub(count(pre2, c, d), count(pre1, b + 1, d))
            return bool(cnt1) and bool(cnt2) and cnt1 == cnt2

        n = len(s)
        m = n // 2
        t = s[m:][::-1]
        s = s[:m]
        pre1 = [[0] * 26 for _ in range(m + 1)]
        pre2 = [[0] * 26 for _ in range(m + 1)]
        diff = [0] * (m + 1)
        for i, (c1, c2) in enumerate(zip(s, t), 1):
            pre1[i] = pre1[i - 1][:]
            pre2[i] = pre2[i - 1][:]
            pre1[i][ord(c1) - ord("a")] += 1
            pre2[i][ord(c2) - ord("a")] += 1
            diff[i] = diff[i - 1] + int(c1 != c2)
        ans = []
        for a, b, c, d in queries:
            c, d = n - 1 - d, n - 1 - c
            ok = (
                check(pre1, pre2, a, b, c, d)
                if a <= c
                else check(pre2, pre1, c, d, a, b)
            )
            ans.append(ok)
        return ans

Continue Practicing

#2949 count beautiful substrings ii #2947 count beautiful substrings i #2982 find longest special substring that occurs thrice ii