2983. Palindrome Rearrangement Queries
Problem Description
You are given a string s
with even length n
. The goal is to determine if you can make s
a palindrome by rearranging characters within specific allowed ranges.
For each query queries[i] = [a_i, b_i, c_i, d_i]
, you can perform two operations:
- Rearrange characters within substring
s[a_i:b_i]
(inclusive), where0 <= a_i <= b_i < n/2
(first half of string) - Rearrange characters within substring
s[c_i:d_i]
(inclusive), wheren/2 <= c_i <= d_i < n
(second half of string)
The key insight is that to form a palindrome, the first half and the reversed second half of the string must become identical after rearrangements.
The solution transforms the problem by:
- Splitting string
s
into two halves: the first half remains ass
, and the second half is reversed to become stringt
- Converting each query's second half indices
[c_i, d_i]
to[n-1-d_i, n-1-c_i]
to work with the reversed string - Checking if rearranging
s[a_i:b_i]
andt[c_i:d_i]
can make stringss
andt
equal
The algorithm uses prefix sums to track character frequencies and checks various conditions based on how the rearrangeable intervals overlap:
-
Non-rearrangeable parts must match: Characters outside the query ranges must already be equal between
s
andt
-
Contained intervals (
d_i <= b_i
): If one interval contains the other, both substrings must have identical character counts -
Non-overlapping intervals (
b_i < c_i
): The gap between intervals must already match, and each interval must have matching character counts with its corresponding position -
Overlapping intervals (
c_i <= b_i < d_i
): The character differences must balance out - characters ins[a_i:b_i]
not matched byt[a_i:c_i-1]
must equal characters int[c_i:d_i]
not matched bys[b_i+1:d_i]
Each query is evaluated independently, returning true
if the palindrome can be formed, false
otherwise.
Intuition
The key insight starts with understanding what makes a string a palindrome - the first half must mirror the second half. Since we can only rearrange characters within specific ranges, we need to think about when rearrangement is sufficient to create this mirror effect.
First, let's simplify the problem. Instead of thinking about making the entire string a palindrome, we can transform it into checking if two strings can become equal. We split the original string s
into two halves and reverse the second half to get string t
. Now, making s
a palindrome is equivalent to making these two strings identical.
Why does this transformation help? Because now we're dealing with two aligned strings where position i
in the first string should match position i
in the second string for a palindrome. Each query allows us to rearrange a segment in the first half (now in string s
) and a segment in the second half (now in string t
after reversal and index adjustment).
The next realization is that rearranging characters within a range only changes the order, not the character counts. So if we want two ranges to become equal after rearrangement, they must contain the same characters with the same frequencies. This immediately suggests using character frequency counting.
But we can't just check the rearrangeable ranges - we also need to ensure that the parts we're NOT allowed to rearrange are already matching. This leads to the critical insight: we need to check that characters outside our rearrangeable ranges are already in the correct positions for a palindrome.
The complexity arises from how the two rearrangeable ranges can relate to each other:
- They might not overlap at all (after alignment)
- One might contain the other
- They might partially overlap
Each case requires different logic because the "fixed" parts (that we can't rearrange) are different. For overlapping ranges, we need to be particularly careful - some positions can be rearranged in string s
but not in t
, and vice versa. The characters that can only be rearranged on one side must be balanced by the appropriate characters on the other side.
Using prefix sums allows us to efficiently compute character counts for any substring, making it feasible to check all these conditions for each query without repeatedly counting characters.
Learn more about Prefix Sum patterns.
Solution Approach
The implementation follows a systematic approach using prefix sums and case-by-case analysis:
Data Preprocessing
First, we split the string into two halves and prepare our data structures:
- Split string
s
of lengthn
into first halfs[:m]
and second half (reversed)t = s[m:][::-1]
wherem = n/2
- Build prefix sum arrays
pre1
andpre2
wherepre1[i][j]
counts occurrences of characterj
ins[0:i]
andpre2[i][j]
counts occurrences int[0:i]
- Create difference array
diff[i]
that tracks the number of mismatched characters betweens[0:i]
andt[0:i]
Helper Functions
count(pre, i, j)
: Returns character frequency counts for substring [i, j]
using prefix sums:
return [x - y for x, y in zip(pre[j + 1], pre[i])]
sub(cnt1, cnt2)
: Subtracts character counts, returning empty list if any count goes negative:
for x, y in zip(cnt1, cnt2):
if x - y < 0:
return []
res.append(x - y)
Main Check Function
The check
function handles four cases based on interval relationships:
Case 1: Boundary Check
if diff[a] > 0 or diff[m] - diff[max(b, d) + 1] > 0:
return False
Ensures characters before position a
and after position max(b, d)
are already matching.
Case 2: Contained Intervals (d <= b
)
if d <= b: return count(pre1, a, b) == count(pre2, a, b)
When one interval contains the other, both substrings must have identical character counts.
Case 3: Non-overlapping Intervals (b < c
)
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))
The gap between intervals must match, and each interval must have matching character counts.
Case 4: Overlapping Intervals (c <= b < 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
Characters in s[a:b]
not matched by t[a:c-1]
must equal characters in t[c:d]
not matched by s[b+1:d]
.
Query Processing
For each query [a, b, c, d]
:
- Transform second half indices:
c, d = n - 1 - d, n - 1 - c
- Ensure
a <= c
for consistency (swap if needed) - Call
check
function with appropriate parameters - Return boolean result
The time complexity is O(26 * m)
for preprocessing and O(26)
per query, where m = n/2
. The space complexity is O(26 * m)
for the prefix sum arrays.
Ready to land your dream job?
Unlock your dream job with a 5-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's walk through a concrete example to understand how the solution works.
Input: s = "abcdbadc"
, query = [0, 1, 4, 5]
Step 1: Transform the Problem
- Original string:
s = "abcdbadc"
(length 8) - Split into halves: first half =
"abcd"
, second half ="badc"
- Reverse second half to get
t = "cdab"
- Now we work with
s = "abcd"
andt = "cdab"
Step 2: Transform Query Indices
- Original query:
[0, 1, 4, 5]
means we can rearranges[0:1]
ands[4:5]
- For the second half indices
[4, 5]
, we transform them for the reversed string:c = 8 - 1 - 5 = 2
d = 8 - 1 - 4 = 3
- Transformed query: we can rearrange
s[0:1]
(which is"ab"
) andt[2:3]
(which is"ab"
)
Step 3: Build Prefix Sums
For s = "abcd"
:
pre1[0]
= [0,0,0,0] (26 zeros, showing only first 4 for brevity)pre1[1]
= [1,0,0,0] (saw 'a')pre1[2]
= [1,1,0,0] (saw 'a','b')pre1[3]
= [1,1,1,0] (saw 'a','b','c')pre1[4]
= [1,1,1,1] (saw 'a','b','c','d')
For t = "cdab"
:
pre2[0]
= [0,0,0,0]pre2[1]
= [0,0,1,0] (saw 'c')pre2[2]
= [0,0,1,1] (saw 'c','d')pre2[3]
= [1,0,1,1] (saw 'c','d','a')pre2[4]
= [1,1,1,1] (saw 'c','d','a','b')
Step 4: Build Difference Array
diff[0]
= 0 (no characters compared yet)diff[1]
= 1 (s[0]='a'
≠t[0]='c'
)diff[2]
= 2 (s[1]='b'
≠t[1]='d'
)diff[3]
= 2 (s[2]='c'
=t[2]='a'
, but previous mismatches remain)diff[4]
= 2 (s[3]='d'
≠t[3]='b'
)
Step 5: Apply Check Function
With a=0, b=1, c=2, d=3
:
-
Boundary check:
diff[0] = 0
✓ (no mismatches before position 0)diff[4] - diff[max(1,3)+1] = 2 - 2 = 0
✓ (no mismatches after position 3)
-
Determine case: Since
b=1 < c=2
, we have non-overlapping intervals. -
Non-overlapping check:
- Gap check:
diff[2] - diff[2] = 2 - 2 = 0
✓ (positions between intervals match) - First interval:
count(pre1, 0, 1) = [1,1,0,0]
vscount(pre2, 0, 1) = [0,0,1,1]
✗
- Gap check:
The character counts don't match! s[0:1]="ab"
has different characters than t[0:1]="cd"
.
Result: False
- we cannot make this string a palindrome with this query.
Why it fails: To form a palindrome, after rearrangement, positions 0-1 in the first half need to match positions 0-1 in the reversed second half. But "ab"
and "cd"
have completely different characters, so no amount of rearrangement can make them equal.
Solution Implementation
1class Solution:
2 def canMakePalindromeQueries(self, s: str, queries: List[List[int]]) -> List[bool]:
3 """
4 Determines if palindromes can be formed for given query ranges.
5
6 Args:
7 s: Input string to check
8 queries: List of query ranges [a, b, c, d]
9
10 Returns:
11 List of boolean values indicating if each query can form a palindrome
12 """
13
14 def get_char_count(prefix_sum: List[List[int]], start: int, end: int) -> List[int]:
15 """
16 Get character frequency count for substring s[start:end+1] using prefix sums.
17
18 Args:
19 prefix_sum: Prefix sum array for character counts
20 start: Starting index (inclusive)
21 end: Ending index (inclusive)
22
23 Returns:
24 List of 26 integers representing character frequencies
25 """
26 return [prefix_sum[end + 1][i] - prefix_sum[start][i]
27 for i in range(26)]
28
29 def subtract_counts(count1: List[int], count2: List[int]) -> List[int]:
30 """
31 Subtract character counts (count1 - count2).
32
33 Args:
34 count1: First character count array
35 count2: Second character count array
36
37 Returns:
38 Difference array if all values are non-negative, empty list otherwise
39 """
40 result = []
41 for freq1, freq2 in zip(count1, count2):
42 if freq1 - freq2 < 0:
43 return [] # Invalid subtraction (negative count)
44 result.append(freq1 - freq2)
45 return result
46
47 def check_palindrome_possible(
48 prefix1: List[List[int]],
49 prefix2: List[List[int]],
50 left1: int,
51 right1: int,
52 left2: int,
53 right2: int
54 ) -> bool:
55 """
56 Check if palindrome can be formed with given ranges.
57
58 Args:
59 prefix1: Prefix sum for first half
60 prefix2: Prefix sum for second half (reversed)
61 left1, right1: Range in first half
62 left2, right2: Range in second half
63
64 Returns:
65 True if palindrome can be formed, False otherwise
66 """
67 # Check if there are mismatches outside the query ranges
68 if mismatch_count[left1] > 0 or mismatch_count[half_len] - mismatch_count[max(right1, right2) + 1] > 0:
69 return False
70
71 # Case 1: Second range is completely within first range
72 if right2 <= right1:
73 return get_char_count(prefix1, left1, right1) == get_char_count(prefix2, left1, right1)
74
75 # Case 2: Ranges don't overlap
76 if right1 < left2:
77 # Check no mismatches between ranges
78 if mismatch_count[left2] - mismatch_count[right1 + 1] != 0:
79 return False
80 # Check character counts match for both ranges
81 return (get_char_count(prefix1, left1, right1) == get_char_count(prefix2, left1, right1) and
82 get_char_count(prefix1, left2, right2) == get_char_count(prefix2, left2, right2))
83
84 # Case 3: Ranges overlap
85 # Calculate excess characters from first range
86 excess1 = subtract_counts(
87 get_char_count(prefix1, left1, right1),
88 get_char_count(prefix2, left1, left2 - 1)
89 )
90 # Calculate excess characters from second range
91 excess2 = subtract_counts(
92 get_char_count(prefix2, left2, right2),
93 get_char_count(prefix1, right1 + 1, right2)
94 )
95 # Both excesses must be valid and equal
96 return bool(excess1) and bool(excess2) and excess1 == excess2
97
98 # Initialize variables
99 string_length = len(s)
100 half_len = string_length // 2
101
102 # Split string into two halves (second half reversed)
103 first_half = s[:half_len]
104 second_half = s[half_len:][::-1]
105
106 # Build prefix sum arrays for character counts
107 prefix_sum1 = [[0] * 26 for _ in range(half_len + 1)]
108 prefix_sum2 = [[0] * 26 for _ in range(half_len + 1)]
109 mismatch_count = [0] * (half_len + 1)
110
111 # Populate prefix sums and mismatch counts
112 for i in range(half_len):
113 char1, char2 = first_half[i], second_half[i]
114
115 # Copy previous prefix sum
116 prefix_sum1[i + 1] = prefix_sum1[i][:]
117 prefix_sum2[i + 1] = prefix_sum2[i][:]
118
119 # Update character counts
120 prefix_sum1[i + 1][ord(char1) - ord('a')] += 1
121 prefix_sum2[i + 1][ord(char2) - ord('a')] += 1
122
123 # Update mismatch count
124 mismatch_count[i + 1] = mismatch_count[i] + (1 if char1 != char2 else 0)
125
126 # Process queries
127 result = []
128 for a, b, c, d in queries:
129 # Convert second range indices (c, d) to match reversed second half
130 c_rev, d_rev = string_length - 1 - d, string_length - 1 - c
131
132 # Check palindrome possibility (normalize so first range starts earlier)
133 if a <= c_rev:
134 is_possible = check_palindrome_possible(prefix_sum1, prefix_sum2, a, b, c_rev, d_rev)
135 else:
136 is_possible = check_palindrome_possible(prefix_sum2, prefix_sum1, c_rev, d_rev, a, b)
137
138 result.append(is_possible)
139
140 return result
141
1class Solution {
2 public boolean[] canMakePalindromeQueries(String s, int[][] queries) {
3 int totalLength = s.length();
4 int halfLength = totalLength / 2;
5
6 // Split string into two halves: first half and reversed second half
7 String firstHalf = s.substring(0, halfLength);
8 String secondHalfReversed = new StringBuilder(s.substring(halfLength)).reverse().toString();
9
10 // Prefix sum arrays for character counts in both halves
11 int[][] firstHalfPrefixCount = new int[halfLength + 1][26];
12 int[][] secondHalfPrefixCount = new int[halfLength + 1][26];
13
14 // Prefix sum array for number of mismatches between the two halves
15 int[] mismatchPrefix = new int[halfLength + 1];
16
17 // Initialize prefix count arrays
18 firstHalfPrefixCount[0] = new int[26];
19 secondHalfPrefixCount[0] = new int[26];
20
21 // Build prefix sum arrays
22 for (int i = 1; i <= halfLength; i++) {
23 // Copy previous counts
24 firstHalfPrefixCount[i] = firstHalfPrefixCount[i - 1].clone();
25 secondHalfPrefixCount[i] = secondHalfPrefixCount[i - 1].clone();
26
27 // Increment count for current character
28 firstHalfPrefixCount[i][firstHalf.charAt(i - 1) - 'a']++;
29 secondHalfPrefixCount[i][secondHalfReversed.charAt(i - 1) - 'a']++;
30
31 // Update mismatch count
32 boolean charactersMatch = firstHalf.charAt(i - 1) == secondHalfReversed.charAt(i - 1);
33 mismatchPrefix[i] = mismatchPrefix[i - 1] + (charactersMatch ? 0 : 1);
34 }
35
36 // Process each query
37 boolean[] results = new boolean[queries.length];
38 for (int i = 0; i < queries.length; i++) {
39 int[] query = queries[i];
40 int leftStart = query[0];
41 int leftEnd = query[1];
42
43 // Convert right range indices to work with reversed second half
44 int rightStart = totalLength - 1 - query[3];
45 int rightEnd = totalLength - 1 - query[2];
46
47 // Check if the ranges can form a palindrome
48 // Ensure leftStart <= rightStart for consistent processing
49 if (leftStart <= rightStart) {
50 results[i] = check(firstHalfPrefixCount, secondHalfPrefixCount, mismatchPrefix,
51 leftStart, leftEnd, rightStart, rightEnd);
52 } else {
53 results[i] = check(secondHalfPrefixCount, firstHalfPrefixCount, mismatchPrefix,
54 rightStart, rightEnd, leftStart, leftEnd);
55 }
56 }
57
58 return results;
59 }
60
61 private boolean check(int[][] prefixCount1, int[][] prefixCount2, int[] mismatchPrefix,
62 int rangeStart1, int rangeEnd1, int rangeStart2, int rangeEnd2) {
63 // Check if there are mismatches before the first range or after both ranges
64 boolean hasMismatchBeforeFirstRange = mismatchPrefix[rangeStart1] > 0;
65 boolean hasMismatchAfterBothRanges = mismatchPrefix[mismatchPrefix.length - 1] -
66 mismatchPrefix[Math.max(rangeEnd1, rangeEnd2) + 1] > 0;
67
68 if (hasMismatchBeforeFirstRange || hasMismatchAfterBothRanges) {
69 return false;
70 }
71
72 // Case 1: Second range is completely within the first range
73 if (rangeEnd2 <= rangeEnd1) {
74 // Both ranges must have the same character counts
75 return Arrays.equals(getCharacterCount(prefixCount1, rangeStart1, rangeEnd1),
76 getCharacterCount(prefixCount2, rangeStart1, rangeEnd1));
77 }
78
79 // Case 2: Ranges don't overlap
80 if (rangeEnd1 < rangeStart2) {
81 // Check no mismatches between ranges
82 boolean noMismatchBetweenRanges = mismatchPrefix[rangeStart2] - mismatchPrefix[rangeEnd1 + 1] == 0;
83
84 // Check character counts match for both ranges independently
85 boolean range1Matches = Arrays.equals(getCharacterCount(prefixCount1, rangeStart1, rangeEnd1),
86 getCharacterCount(prefixCount2, rangeStart1, rangeEnd1));
87 boolean range2Matches = Arrays.equals(getCharacterCount(prefixCount1, rangeStart2, rangeEnd2),
88 getCharacterCount(prefixCount2, rangeStart2, rangeEnd2));
89
90 return noMismatchBetweenRanges && range1Matches && range2Matches;
91 }
92
93 // Case 3: Ranges overlap
94 // Calculate excess characters in each range after accounting for the overlap
95 int[] excessInRange1 = subtractCounts(getCharacterCount(prefixCount1, rangeStart1, rangeEnd1),
96 getCharacterCount(prefixCount2, rangeStart1, rangeStart2 - 1));
97 int[] excessInRange2 = subtractCounts(getCharacterCount(prefixCount2, rangeStart2, rangeEnd2),
98 getCharacterCount(prefixCount1, rangeEnd1 + 1, rangeEnd2));
99
100 // Both excess counts must be valid (non-negative) and equal
101 return excessInRange1 != null && excessInRange2 != null && Arrays.equals(excessInRange1, excessInRange2);
102 }
103
104 private int[] getCharacterCount(int[][] prefixCount, int startIndex, int endIndex) {
105 int[] characterCount = new int[26];
106
107 // Calculate character counts in range [startIndex, endIndex]
108 for (int i = 0; i < 26; i++) {
109 characterCount[i] = prefixCount[endIndex + 1][i] - prefixCount[startIndex][i];
110 }
111
112 return characterCount;
113 }
114
115 private int[] subtractCounts(int[] count1, int[] count2) {
116 int[] difference = new int[26];
117
118 // Subtract count2 from count1
119 for (int i = 0; i < 26; i++) {
120 difference[i] = count1[i] - count2[i];
121
122 // Return null if any count becomes negative (invalid subtraction)
123 if (difference[i] < 0) {
124 return null;
125 }
126 }
127
128 return difference;
129 }
130}
131
1class Solution {
2public:
3 vector<bool> canMakePalindromeQueries(string s, vector<vector<int>>& queries) {
4 int n = s.length();
5 int halfLen = n / 2;
6
7 // Split the string into two halves
8 // secondHalf is reversed to align with firstHalf for comparison
9 string secondHalf = string(s.begin() + halfLen, s.end());
10 reverse(secondHalf.begin(), secondHalf.end());
11 string firstHalf = string(s.begin(), s.begin() + halfLen);
12
13 // Prefix sum arrays for character frequencies in both halves
14 vector<vector<int>> prefixFirst(halfLen + 1, vector<int>(26));
15 vector<vector<int>> prefixSecond(halfLen + 1, vector<int>(26));
16
17 // Prefix sum array for counting mismatches between the two halves
18 vector<int> mismatchCount(halfLen + 1, 0);
19
20 // Build prefix sum arrays
21 for (int i = 1; i <= halfLen; ++i) {
22 // Copy previous frequency counts
23 prefixFirst[i] = prefixFirst[i - 1];
24 prefixSecond[i] = prefixSecond[i - 1];
25
26 // Update frequency for current character
27 ++prefixFirst[i][firstHalf[i - 1] - 'a'];
28 ++prefixSecond[i][secondHalf[i - 1] - 'a'];
29
30 // Update mismatch count
31 mismatchCount[i] = mismatchCount[i - 1] +
32 (firstHalf[i - 1] == secondHalf[i - 1] ? 0 : 1);
33 }
34
35 // Process each query
36 vector<bool> result(queries.size(), false);
37 for (int i = 0; i < queries.size(); ++i) {
38 vector<int> query = queries[i];
39 int leftStart = query[0], leftEnd = query[1];
40
41 // Convert right range indices to corresponding positions in reversed second half
42 int rightStart = n - 1 - query[3], rightEnd = n - 1 - query[2];
43
44 // Check based on which range starts first
45 result[i] = (leftStart <= rightStart) ?
46 checkValidity(prefixFirst, prefixSecond, mismatchCount,
47 leftStart, leftEnd, rightStart, rightEnd) :
48 checkValidity(prefixSecond, prefixFirst, mismatchCount,
49 rightStart, rightEnd, leftStart, leftEnd);
50 }
51 return result;
52 }
53
54private:
55 bool checkValidity(const vector<vector<int>>& prefix1,
56 const vector<vector<int>>& prefix2,
57 const vector<int>& mismatchCount,
58 int start1, int end1, int start2, int end2) {
59
60 // Check if there are mismatches before the first range or after both ranges
61 if (mismatchCount[start1] > 0 ||
62 mismatchCount[mismatchCount.size() - 1] - mismatchCount[max(end1, end2) + 1] > 0) {
63 return false;
64 }
65
66 // Case 1: Second range is completely within the first range
67 if (end2 <= end1) {
68 return getCharCount(prefix1, start1, end1) == getCharCount(prefix2, start1, end1);
69 }
70
71 // Case 2: Ranges don't overlap
72 if (end1 < start2) {
73 // Check no mismatches between ranges
74 // Check character counts match for both ranges independently
75 return mismatchCount[start2] - mismatchCount[end1 + 1] == 0 &&
76 getCharCount(prefix1, start1, end1) == getCharCount(prefix2, start1, end1) &&
77 getCharCount(prefix1, start2, end2) == getCharCount(prefix2, start2, end2);
78 }
79
80 // Case 3: Ranges overlap
81 // Calculate excess characters from first range after matching with second range's prefix
82 vector<int> excess1 = subtractCounts(getCharCount(prefix1, start1, end1),
83 getCharCount(prefix2, start1, start2 - 1));
84 // Calculate excess characters from second range after matching with first range's suffix
85 vector<int> excess2 = subtractCounts(getCharCount(prefix2, start2, end2),
86 getCharCount(prefix1, end1 + 1, end2));
87
88 // Both excesses should be valid (non-negative) and equal
89 return excess1 != vector<int>() && excess2 != vector<int>() && excess1 == excess2;
90 }
91
92 // Get character frequency count for range [startIdx, endIdx]
93 vector<int> getCharCount(const vector<vector<int>>& prefix, int startIdx, int endIdx) {
94 vector<int> charFreq(26);
95 for (int k = 0; k < 26; ++k) {
96 charFreq[k] = prefix[endIdx + 1][k] - prefix[startIdx][k];
97 }
98 return charFreq;
99 }
100
101 // Subtract second character count from first
102 // Returns empty vector if any count becomes negative
103 vector<int> subtractCounts(const vector<int>& count1, const vector<int>& count2) {
104 vector<int> result(26);
105 for (int i = 0; i < 26; ++i) {
106 result[i] = count1[i] - count2[i];
107 if (result[i] < 0) {
108 return vector<int>(); // Invalid subtraction
109 }
110 }
111 return result;
112 }
113};
114
1/**
2 * Determines if palindromes can be formed after rearranging substrings based on queries
3 * @param s - Input string to be checked
4 * @param queries - Array of queries, each containing 4 indices [a, b, c, d]
5 * @returns Array of booleans indicating if each query can form a palindrome
6 */
7function canMakePalindromeQueries(s: string, queries: number[][]): boolean[] {
8 const stringLength: number = s.length;
9 const halfLength: number = stringLength >> 1;
10
11 // Split string into two halves, reverse the second half
12 const reversedSecondHalf: string = s.slice(halfLength).split('').reverse().join('');
13 const firstHalf: string = s.slice(0, halfLength);
14
15 // Initialize prefix sum arrays for character counts
16 const firstHalfPrefixSum: number[][] = Array.from({ length: halfLength + 1 }, () => Array(26).fill(0));
17 const secondHalfPrefixSum: number[][] = Array.from({ length: halfLength + 1 }, () => Array(26).fill(0));
18
19 // Track positions where characters differ between halves
20 const diffCount: number[] = Array(halfLength + 1).fill(0);
21
22 // Build prefix sums and difference array
23 for (let i = 1; i <= halfLength; ++i) {
24 // Copy previous prefix sum values
25 firstHalfPrefixSum[i] = [...firstHalfPrefixSum[i - 1]];
26 secondHalfPrefixSum[i] = [...secondHalfPrefixSum[i - 1]];
27
28 // Update character counts
29 ++firstHalfPrefixSum[i][firstHalf.charCodeAt(i - 1) - 'a'.charCodeAt(0)];
30 ++secondHalfPrefixSum[i][reversedSecondHalf.charCodeAt(i - 1) - 'a'.charCodeAt(0)];
31
32 // Update difference count
33 diffCount[i] = diffCount[i - 1] + (firstHalf[i - 1] === reversedSecondHalf[i - 1] ? 0 : 1);
34 }
35
36 // Process each query
37 const results: boolean[] = Array(queries.length).fill(false);
38 for (let i = 0; i < queries.length; ++i) {
39 const currentQuery: number[] = queries[i];
40 const [startFirst, endFirst] = [currentQuery[0], currentQuery[1]];
41 const [startSecond, endSecond] = [stringLength - 1 - currentQuery[3], stringLength - 1 - currentQuery[2]];
42
43 // Check based on which range starts first
44 results[i] = startFirst <= startSecond ?
45 check(firstHalfPrefixSum, secondHalfPrefixSum, diffCount, startFirst, endFirst, startSecond, endSecond) :
46 check(secondHalfPrefixSum, firstHalfPrefixSum, diffCount, startSecond, endSecond, startFirst, endFirst);
47 }
48
49 return results;
50}
51
52/**
53 * Checks if the given ranges can form a palindrome after rearrangement
54 * @param prefixSum1 - Prefix sum array for first half
55 * @param prefixSum2 - Prefix sum array for second half
56 * @param diffArray - Array tracking differences between halves
57 * @param rangeStart1 - Start index of first range
58 * @param rangeEnd1 - End index of first range
59 * @param rangeStart2 - Start index of second range
60 * @param rangeEnd2 - End index of second range
61 * @returns True if palindrome can be formed, false otherwise
62 */
63function check(
64 prefixSum1: number[][],
65 prefixSum2: number[][],
66 diffArray: number[],
67 rangeStart1: number,
68 rangeEnd1: number,
69 rangeStart2: number,
70 rangeEnd2: number,
71): boolean {
72 // Check if there are differences outside the query ranges
73 if (diffArray[rangeStart1] > 0 || diffArray[diffArray.length - 1] - diffArray[Math.max(rangeEnd1, rangeEnd2) + 1] > 0) {
74 return false;
75 }
76
77 // Case 1: Second range is within or equal to first range
78 if (rangeEnd2 <= rangeEnd1) {
79 return arraysEqual(count(prefixSum1, rangeStart1, rangeEnd1), count(prefixSum2, rangeStart1, rangeEnd1));
80 }
81
82 // Case 2: Ranges don't overlap
83 if (rangeEnd1 < rangeStart2) {
84 return (
85 diffArray[rangeStart2] - diffArray[rangeEnd1 + 1] === 0 &&
86 arraysEqual(count(prefixSum1, rangeStart1, rangeEnd1), count(prefixSum2, rangeStart1, rangeEnd1)) &&
87 arraysEqual(count(prefixSum1, rangeStart2, rangeEnd2), count(prefixSum2, rangeStart2, rangeEnd2))
88 );
89 }
90
91 // Case 3: Ranges overlap
92 const remainingChars1: number[] | null = sub(count(prefixSum1, rangeStart1, rangeEnd1), count(prefixSum2, rangeStart1, rangeStart2 - 1));
93 const remainingChars2: number[] | null = sub(count(prefixSum2, rangeStart2, rangeEnd2), count(prefixSum1, rangeEnd1 + 1, rangeEnd2));
94
95 return remainingChars1 !== null && remainingChars2 !== null && arraysEqual(remainingChars1, remainingChars2);
96}
97
98/**
99 * Counts characters in a range using prefix sums
100 * @param prefixSum - Prefix sum array
101 * @param startIndex - Start index of range (inclusive)
102 * @param endIndex - End index of range (inclusive)
103 * @returns Array of character counts for each letter
104 */
105function count(prefixSum: number[][], startIndex: number, endIndex: number): number[] {
106 const charCounts: number[] = new Array(26).fill(0);
107 for (let letterIndex = 0; letterIndex < 26; ++letterIndex) {
108 charCounts[letterIndex] = prefixSum[endIndex + 1][letterIndex] - prefixSum[startIndex][letterIndex];
109 }
110 return charCounts;
111}
112
113/**
114 * Subtracts character counts of second array from first array
115 * @param counts1 - First character count array
116 * @param counts2 - Second character count array
117 * @returns Difference array if valid (no negative values), null otherwise
118 */
119function sub(counts1: number[], counts2: number[]): number[] | null {
120 const difference: number[] = new Array(26).fill(0);
121 for (let i = 0; i < 26; ++i) {
122 difference[i] = counts1[i] - counts2[i];
123 if (difference[i] < 0) {
124 return null;
125 }
126 }
127 return difference;
128}
129
130/**
131 * Checks if two arrays are equal
132 * @param array1 - First array to compare
133 * @param array2 - Second array to compare
134 * @returns True if arrays are equal, false otherwise
135 */
136function arraysEqual(array1: number[], array2: number[]): boolean {
137 return JSON.stringify(array1) === JSON.stringify(array2);
138}
139
Time and Space Complexity
Time Complexity: O((n + q) × |Σ|)
The time complexity breaks down as follows:
- Building the prefix sum arrays
pre1
andpre2
: We iterate throughm = n/2
characters, and for each character, we copy the previous prefix array which takesO(|Σ|)
time. This gives usO(n × |Σ|)
. - Building the difference array
diff
:O(n)
time. - Processing queries: For each of the
q
queries:- The
count
function performs subtraction of two arrays of size|Σ|
, takingO(|Σ|)
time. - The
sub
function also operates on arrays of size|Σ|
, takingO(|Σ|)
time. - The
check
function callscount
andsub
a constant number of times, resulting inO(|Σ|)
time per query. - Total for all queries:
O(q × |Σ|)
- The
- Overall time complexity:
O(n × |Σ|) + O(q × |Σ|) = O((n + q) × |Σ|)
Where |Σ| = 26
for lowercase English letters.
Space Complexity: O(n × |Σ|)
The space complexity breaks down as follows:
- Prefix sum arrays
pre1
andpre2
: Each contains(m + 1)
arrays of size26
, wherem = n/2
. This gives us2 × (n/2 + 1) × 26 = O(n × |Σ|)
. - Difference array
diff
:O(n)
space. - Temporary variables in functions (
cnt1
,cnt2
,res
):O(|Σ|)
space. - Answer array
ans
:O(q)
space. - Overall space complexity:
O(n × |Σ|)
dominates.
Where |Σ| = 26
for lowercase English letters.
Learn more about how to find time and space complexity quickly.
Common Pitfalls
1. Index Transformation Confusion
One of the most common mistakes is incorrectly transforming the second half indices when working with the reversed string. The transformation c, d = n - 1 - d, n - 1 - c
is counterintuitive because we need to both reverse the string AND swap the bounds.
Pitfall Example:
# Wrong: Only reversing without swapping c_rev = n - 1 - c d_rev = n - 1 - d # This gives wrong range! # Wrong: Forgetting to adjust for 0-based indexing c_rev = n - d d_rev = n - c
Solution:
Always remember that when reversing a substring [c, d]
in the second half:
- The character at position
d
becomes the leftmost after reversal - The character at position
c
becomes the rightmost after reversal - Therefore:
c_rev = n - 1 - d
andd_rev = n - 1 - c
2. Mishandling the Overlapping Range Case
When ranges overlap (c <= b < d
), the subtraction logic for excess characters is prone to errors. A common mistake is not properly handling the case where subtraction yields negative values.
Pitfall Example:
# Wrong: Not checking for negative counts
excess1 = [x - y for x, y in zip(count1, count2)]
excess2 = [x - y for x, y in zip(count3, count4)]
return excess1 == excess2 # May compare invalid negative counts!
Solution: Always validate that subtraction doesn't produce negative counts:
def subtract_counts(count1, count2):
result = []
for freq1, freq2 in zip(count1, count2):
if freq1 - freq2 < 0:
return [] # Return empty list to indicate invalid
result.append(freq1 - freq2)
return result
# Then check if both results are valid before comparing
return bool(excess1) and bool(excess2) and excess1 == excess2
3. Off-by-One Errors in Prefix Sum Calculations
Prefix sum arrays are 1-indexed (size m+1
for string of length m
), which can lead to boundary errors.
Pitfall Example:
# Wrong: Using wrong indices for prefix sum
count = prefix[j] - prefix[i] # Should be prefix[j+1] - prefix[i]
# Wrong: Not handling edge cases
mismatch_after = diff[m] - diff[max(b, d)] # Missing +1
Solution: Be consistent with prefix sum indexing:
prefix[i]
contains counts for substring[0, i-1]
- To get counts for
[i, j]
, useprefix[j+1] - prefix[i]
- Always add 1 when accessing the "after" position
4. Incorrect Boundary Validation
Failing to properly check that non-rearrangeable parts already match can lead to false positives.
Pitfall Example:
# Wrong: Only checking one boundary if diff[a] > 0: return False # Forgot to check the part after max(b, d)!
Solution: Always validate both boundaries:
# Check before the first rearrangeable position
if mismatch_count[left1] > 0:
return False
# Check after the last rearrangeable position
if mismatch_count[half_len] - mismatch_count[max(right1, right2) + 1] > 0:
return False
5. Forgetting to Normalize Query Order
When comparing ranges from both halves, the code assumes a consistent ordering (first range starts earlier). Forgetting to swap when necessary leads to incorrect results.
Pitfall Example:
# Wrong: Always using a, b as first range is_possible = check_palindrome_possible(prefix1, prefix2, a, b, c_rev, d_rev)
Solution: Normalize the order before checking:
if a <= c_rev: is_possible = check_palindrome_possible(prefix_sum1, prefix_sum2, a, b, c_rev, d_rev) else: # Swap the ranges and prefix arrays is_possible = check_palindrome_possible(prefix_sum2, prefix_sum1, c_rev, d_rev, a, b)
Which algorithm should you use to find a node that is close to the root of the tree?
Recommended Readings
Prefix Sum The prefix sum is an incredibly powerful and straightforward technique Its primary goal is to allow for constant time range sum queries on an array What is Prefix Sum The prefix sum of an array at index i is the sum of all numbers from index 0 to i By
Coding Interview Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https assets algo monster recursion jpg You first call Ben and ask
Want a Structured Path to Master System Design Too? Don’t Miss This!