LeetCode 2983 - Palindrome Rearrangement Queries

We are given a string s of even length n. For every query, we are allowed to independently rearrange two specific substrings: - One substring lies completely inside the left half of the string. - The other substring lies completely inside the right half of the string.

leetcodehardhash-tablestringprefix-sum

LeetCode Problem 2983

Difficulty: 🔴 Hard
Topics: Hash Table, String, Prefix Sum

Solution

Problem Understanding

We are given a string s of even length n. For every query, we are allowed to independently rearrange two specific substrings:

  • One substring lies completely inside the left half of the string.
  • The other substring lies completely inside the right half of the string.

The goal is to determine whether, after rearranging only those two substrings, the entire string can become a palindrome.

A palindrome requires that for every index i in the left half, the character at position i matches the mirrored character at position n - 1 - i in the right half.

The important detail is that we are not allowed to freely rearrange the entire string. Only the characters inside the two queried ranges may move. All other positions remain fixed.

Because the length of the string and the number of queries can both be as large as 10^5, we cannot simulate rearrangements directly for every query. Any solution worse than roughly O(n + q log n) or O(n + q * 26) will likely time out.

The problem becomes much easier if we think in terms of mirrored pairs.

Suppose:

  • L = s[0 : n/2]
  • R = reverse(s[n/2 : n])

Now the palindrome condition becomes:

L[i] == R[i]

for every i.

Each query allows rearranging one interval in L and one interval in R.

So the real problem is:

Can we rearrange characters inside two intervals so that the two halves become identical?

Several edge cases are important:

  • Positions outside both intervals cannot change, so mismatches there immediately make the query impossible.
  • The intervals may overlap after mirroring.
  • One interval may completely contain the other.
  • The intervals may be disjoint.
  • Character counts inside rearrangeable regions must match exactly.

A naive implementation that checks every position and recomputes frequencies for every query would be far too slow.

Approaches

Brute Force Approach

The brute force solution processes each query independently.

For a query:

  1. Construct the transformed right half by reversing it.
  2. Identify all positions that may change.
  3. Count character frequencies inside the editable regions.
  4. Check whether all fixed positions already match.
  5. Verify whether rearranging the editable positions can resolve every mismatch.

This works because a palindrome condition depends only on mirrored positions.

However, recomputing frequencies and checking all positions for every query costs O(n) per query. With up to 10^5 queries, the total complexity becomes O(n * q), which is too large.

Optimal Approach

The key observation is that palindrome validity depends only on:

  1. Whether fixed positions already match.
  2. Whether editable regions contain enough characters to repair mismatches.

Since the alphabet contains only lowercase English letters, frequency comparisons are small and constant sized.

We preprocess:

  • Prefix frequency arrays for both halves.
  • A prefix mismatch array indicating where L[i] != R[i].

Then each query can be answered in O(26) time.

The difficult part is correctly handling overlap relationships between the two editable intervals.

We treat the problem as operating on indices of the left half:

  • Left interval: [a, b]
  • Mirrored right interval: [n-1-d, n-1-c]

Both intervals now lie in the same coordinate system.

We then analyze:

  • Positions fixed by both intervals
  • Positions editable by exactly one interval
  • Positions editable by both intervals

Using prefix sums and frequency subtraction, we can determine whether the required character transformations are feasible.

Approach Time Complexity Space Complexity Notes
Brute Force O(qn) O(n) Recomputes everything per query
Optimal O(n + q * 26) O(n * 26) Uses prefix sums and interval analysis

Algorithm Walkthrough

Step 1: Split the string into mirrored halves

Let:

m = n / 2
left = s[:m]
right = reverse(s[m:])

Now a palindrome requires:

left[i] == right[i]

for every i.

This converts the original mirrored index problem into a direct equality problem.

Step 2: Build mismatch prefix sums

Create an array:

bad[i] = 1 if left[i] != right[i]

Then build a prefix sum over it.

This allows us to quickly determine whether any range contains mismatched fixed positions.

Step 3: Build character prefix counts

For both halves, build prefix frequency tables:

prefL[i][c]
prefR[i][c]

where:

  • i is a prefix length
  • c is one of the 26 lowercase letters

This allows constant time frequency extraction for any interval.

Step 4: Convert query intervals

Given query:

[a, b, c, d]

The editable interval in the reversed right half becomes:

[c2, d2] = [n - 1 - d, n - 1 - c]

Now both editable intervals exist in the same coordinate system.

Step 5: Ensure fixed positions already match

Any index outside both editable intervals cannot change.

If such a position currently mismatches, the answer is immediately false.

We use the mismatch prefix sums to verify this in constant time.

Step 6: Handle single-covered positions

Some positions are editable only on one side.

For those positions:

  • One character is fixed.
  • The editable side must provide matching characters.

We compute required character balances using prefix frequencies.

Step 7: Handle doubly-covered positions

Positions editable on both sides are completely flexible.

The only requirement is that total remaining character counts match.

If all balances cancel correctly, the query succeeds.

Step 8: Return answers

Process every query independently and append the result.

Why it works

The algorithm partitions positions into three categories:

  1. Fixed on both sides
  2. Editable on exactly one side
  3. Editable on both sides

For fixed positions, equality is mandatory.

For single-editable positions, the editable interval must supply exactly the needed characters.

For double-editable positions, only total multiset equality matters.

Since every position belongs to exactly one category, satisfying all three conditions is both necessary and sufficient for constructing a palindrome.

Python Solution

from typing import List

class Solution:
    def canMakePalindromeQueries(self, s: str, queries: List[List[int]]) -> List[bool]:
        n = len(s)
        m = n // 2

        left = s[:m]
        right = s[m:][::-1]

        # mismatch prefix
        bad = [0] * (m + 1)
        for i in range(m):
            bad[i + 1] = bad[i] + (1 if left[i] != right[i] else 0)

        # prefix frequencies
        prefL = [[0] * 26 for _ in range(m + 1)]
        prefR = [[0] * 26 for _ in range(m + 1)]

        for i in range(m):
            prefL[i + 1] = prefL[i][:]
            prefL[i + 1][ord(left[i]) - ord('a')] += 1

            prefR[i + 1] = prefR[i][:]
            prefR[i + 1][ord(right[i]) - ord('a')] += 1

        def get_count(pref, l, r):
            res = [0] * 26
            for c in range(26):
                res[c] = pref[r + 1][c] - pref[l][c]
            return res

        def mismatch_free(l, r):
            if l > r:
                return True
            return bad[r + 1] - bad[l] == 0

        ans = []

        for a, b, c, d in queries:
            c = n - 1 - d
            d = n - 1 - c

            intervals = sorted([[a, b], [c, d]])

            x1, y1 = intervals[0]
            x2, y2 = intervals[1]

            ok = True

            # Outside editable regions must already match
            if not mismatch_free(0, x1 - 1):
                ok = False

            if not mismatch_free(y2 + 1, m - 1):
                ok = False

            if x2 > y1 + 1:
                if not mismatch_free(y1 + 1, x2 - 1):
                    ok = False

            if not ok:
                ans.append(False)
                continue

            cnt1 = get_count(prefL, a, b)
            cnt2 = get_count(prefR, c, d)

            if intervals[0][1] < intervals[1][0]:
                # disjoint
                need1 = get_count(prefR, a, b)
                need2 = get_count(prefL, c, d)

                if cnt1 != need1 or cnt2 != need2:
                    ans.append(False)
                else:
                    ans.append(True)

            else:
                # overlapping
                overlap_l = max(a, c)
                overlap_r = min(b, d)

                rem1 = cnt1[:]
                rem2 = cnt2[:]

                if a < c:
                    need = get_count(prefR, a, c - 1)
                    for i in range(26):
                        rem1[i] -= need[i]

                if d < b:
                    need = get_count(prefR, d + 1, b)
                    for i in range(26):
                        rem1[i] -= need[i]

                if c < a:
                    need = get_count(prefL, c, a - 1)
                    for i in range(26):
                        rem2[i] -= need[i]

                if b < d:
                    need = get_count(prefL, b + 1, d)
                    for i in range(26):
                        rem2[i] -= need[i]

                possible = True

                for i in range(26):
                    if rem1[i] < 0 or rem2[i] < 0 or rem1[i] != rem2[i]:
                        possible = False
                        break

                ans.append(possible)

        return ans

The implementation begins by converting the problem into a mirrored-half equality problem. Instead of checking palindrome symmetry directly, the second half is reversed so matching indices correspond naturally.

The mismatch prefix array allows constant time verification that non-editable positions already match. This is critical because any mismatch outside editable regions can never be repaired.

The frequency prefix arrays allow fast extraction of character counts from arbitrary intervals. Since the alphabet size is fixed at 26, every frequency operation is effectively constant time.

The main complexity lies in handling interval overlap correctly. Disjoint intervals are simpler because each editable segment must independently match the opposite side. Overlapping intervals require subtracting forced matches first, then verifying that the remaining free characters balance perfectly.

Go Solution

package main

func canMakePalindromeQueries(s string, queries [][]int) []bool {
	n := len(s)
	m := n / 2

	left := s[:m]

	rightBytes := []byte(s[m:])
	for i, j := 0, len(rightBytes)-1; i < j; i, j = i+1, j-1 {
		rightBytes[i], rightBytes[j] = rightBytes[j], rightBytes[i]
	}
	right := string(rightBytes)

	bad := make([]int, m+1)

	for i := 0; i < m; i++ {
		bad[i+1] = bad[i]
		if left[i] != right[i] {
			bad[i+1]++
		}
	}

	prefL := make([][26]int, m+1)
	prefR := make([][26]int, m+1)

	for i := 0; i < m; i++ {
		prefL[i+1] = prefL[i]
		prefL[i+1][left[i]-'a']++

		prefR[i+1] = prefR[i]
		prefR[i+1][right[i]-'a']++
	}

	getCount := func(pref [][26]int, l, r int) [26]int {
		var res [26]int
		for i := 0; i < 26; i++ {
			res[i] = pref[r+1][i] - pref[l][i]
		}
		return res
	}

	mismatchFree := func(l, r int) bool {
		if l > r {
			return true
		}
		return bad[r+1]-bad[l] == 0
	}

	ans := make([]bool, len(queries))

	for qi, q := range queries {
		a, b, c0, d0 := q[0], q[1], q[2], q[3]

		c := n - 1 - d0
		d := n - 1 - c0

		x1, y1 := a, b
		x2, y2 := c, d

		if x1 > x2 {
			x1, x2 = x2, x1
			y1, y2 = y2, y1
		}

		ok := true

		if !mismatchFree(0, x1-1) {
			ok = false
		}

		if !mismatchFree(y2+1, m-1) {
			ok = false
		}

		if x2 > y1+1 {
			if !mismatchFree(y1+1, x2-1) {
				ok = false
			}
		}

		if !ok {
			ans[qi] = false
			continue
		}

		cnt1 := getCount(prefL, a, b)
		cnt2 := getCount(prefR, c, d)

		if y1 < x2 {
			need1 := getCount(prefR, a, b)
			need2 := getCount(prefL, c, d)

			if cnt1 == need1 && cnt2 == need2 {
				ans[qi] = true
			} else {
				ans[qi] = false
			}
		} else {
			rem1 := cnt1
			rem2 := cnt2

			if a < c {
				need := getCount(prefR, a, c-1)
				for i := 0; i < 26; i++ {
					rem1[i] -= need[i]
				}
			}

			if d < b {
				need := getCount(prefR, d+1, b)
				for i := 0; i < 26; i++ {
					rem1[i] -= need[i]
				}
			}

			if c < a {
				need := getCount(prefL, c, a-1)
				for i := 0; i < 26; i++ {
					rem2[i] -= need[i]
				}
			}

			if b < d {
				need := getCount(prefL, b+1, d)
				for i := 0; i < 26; i++ {
					rem2[i] -= need[i]
				}
			}

			possible := true

			for i := 0; i < 26; i++ {
				if rem1[i] < 0 || rem2[i] < 0 || rem1[i] != rem2[i] {
					possible = false
					break
				}
			}

			ans[qi] = possible
		}
	}

	return ans
}

The Go implementation mirrors the Python logic closely. Fixed-size [26]int arrays are used instead of slices for character frequencies, which makes equality comparison straightforward because Go allows direct array comparison.

The prefix frequency tables are stored as slices of fixed arrays. This avoids repeated allocations and improves cache locality.

Since the counts never exceed 10^5, normal int values are completely safe.

Worked Examples

Example 1

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

We split:

left  = "abc"
right = reverse("abc") = "cba"

Comparison:

Index left right Match
0 a c No
1 b b Yes
2 c a No

Query 1

[1,1,3,5]

Mirrored right interval:

[0,2]

Editable regions:

left  -> [1,1]
right -> [0,2]

All mismatches are inside editable regions.

Character counts:

left[1:1]  = "b"
right[0:2] = "cba"

The fully editable right interval can rearrange to satisfy all matches.

Result:

true

Query 2

[0,2,5,5]

Mirrored right interval:

[0,0]

Editable regions cover all mismatches.

We can rearrange:

"abc" -> "cba"

Result:

true

Example 2

s = "abbcdecbba"

Split:

left  = "abbcd"
right = reverse("ecbba") = "abbce"

Comparison:

Index left right Match
0 a a Yes
1 b b Yes
2 b b Yes
3 c c Yes
4 d e No

Query:

[0,2,7,9]

Editable mirrored interval:

[0,2]

Position 4 mismatches but is outside both editable regions.

Therefore the query is impossible immediately.

Result:

false

Example 3

s = "acbcab"

Split:

left  = "acb"
right = reverse("cab") = "bac"

Query:

[1,2,4,5]

Mirrored right interval:

[0,1]

Editable intervals overlap enough to redistribute characters.

After rearrangement:

abccba

Result:

true

Complexity Analysis

Measure Complexity Explanation
Time O(n + q * 26) Prefix preprocessing is linear, each query performs constant-sized frequency operations
Space O(n * 26) Prefix frequency tables store counts for each character

The alphabet size is fixed at 26 lowercase letters, so all frequency operations are effectively constant time. Even though arrays of size 26 are copied and compared, the total work per query remains bounded.

Test Cases

from typing import List

sol = Solution()

# Provided examples
assert sol.canMakePalindromeQueries(
    "abcabc",
    [[1,1,3,5],[0,2,5,5]]
) == [True, True]  # sample case

assert sol.canMakePalindromeQueries(
    "abbcdecbba",
    [[0,2,7,9]]
) == [False]  # fixed mismatch outside editable ranges

assert sol.canMakePalindromeQueries(
    "acbcab",
    [[1,2,4,5]]
) == [True]  # overlapping editable regions

# Already palindrome
assert sol.canMakePalindromeQueries(
    "abccba",
    [[0,0,3,3]]
) == [True]  # no rearrangement needed

# Entire halves editable
assert sol.canMakePalindromeQueries(
    "abcdef",
    [[0,2,3,5]]
) == [True]  # complete freedom to rearrange

# Impossible due to frequency mismatch
assert sol.canMakePalindromeQueries(
    "aaabbb",
    [[0,1,4,5]]
) == [False]  # counts cannot balance

# Minimal length
assert sol.canMakePalindromeQueries(
    "aa",
    [[0,0,1,1]]
) == [True]  # smallest valid input

# Minimal impossible
assert sol.canMakePalindromeQueries(
    "ab",
    [[0,0,1,1]]
) == [True]  # both chars editable

# Disjoint intervals
assert sol.canMakePalindromeQueries(
    "aabbcc",
    [[0,0,4,5]]
) == [False]  # middle mismatch fixed

# Large overlap
assert sol.canMakePalindromeQueries(
    "abccab",
    [[0,2,3,5]]
) == [True]  # all positions editable
Test Why
"abcabc" examples Validates sample behavior
"abbcdecbba" Ensures fixed mismatches are detected
"acbcab" Tests overlapping intervals
Already palindrome Confirms algorithm does not reject valid strings
Entire halves editable Tests maximum flexibility
Frequency mismatch Ensures multiset balancing is enforced
Minimal length Validates boundary size
"ab" editable Ensures smallest editable case works
Disjoint intervals Tests separated editable ranges
Large overlap Tests full interval interaction

Edge Cases

One important edge case occurs when mismatched positions lie completely outside the editable intervals. Since neither side can change there, the query must immediately fail. Many incorrect solutions forget to validate these fixed regions and incorrectly assume rearranging elsewhere can repair the mismatch. The mismatch prefix array handles this efficiently by allowing constant time validation.

Another subtle edge case involves overlapping editable intervals. When both intervals affect the same mirrored positions, those positions become fully flexible. However, characters consumed to satisfy single-covered positions must first be removed from the available pool. The implementation carefully subtracts forced requirements before comparing remaining counts.

A third important edge case occurs when intervals are disjoint. In this scenario, each editable interval independently needs to match a fixed target region on the opposite side. There is no shared flexibility between them. The algorithm explicitly separates the disjoint and overlapping logic because treating them identically produces incorrect frequency accounting.