Facebook Pixel

2983. Palindrome Rearrangement Queries

HardHash TableStringPrefix Sum
Leetcode Link

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:

  1. Rearrange characters within substring s[a_i:b_i] (inclusive), where 0 <= a_i <= b_i < n/2 (first half of string)
  2. Rearrange characters within substring s[c_i:d_i] (inclusive), where n/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 as s, and the second half is reversed to become string t
  • 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] and t[c_i:d_i] can make strings s and t equal

The algorithm uses prefix sums to track character frequencies and checks various conditions based on how the rearrangeable intervals overlap:

  1. Non-rearrangeable parts must match: Characters outside the query ranges must already be equal between s and t

  2. Contained intervals (d_i <= b_i): If one interval contains the other, both substrings must have identical character counts

  3. 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

  4. Overlapping intervals (c_i <= b_i < d_i): The character differences must balance out - characters in s[a_i:b_i] not matched by t[a_i:c_i-1] must equal characters in t[c_i:d_i] not matched by s[b_i+1:d_i]

Each query is evaluated independently, returning true if the palindrome can be formed, false otherwise.

Quick Interview Experience
Help others by sharing your interview experience
Have you seen this problem before?

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 length n into first half s[:m] and second half (reversed) t = s[m:][::-1] where m = n/2
  • Build prefix sum arrays pre1 and pre2 where pre1[i][j] counts occurrences of character j in s[0:i] and pre2[i][j] counts occurrences in t[0:i]
  • Create difference array diff[i] that tracks the number of mismatched characters between s[0:i] and t[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]:

  1. Transform second half indices: c, d = n - 1 - d, n - 1 - c
  2. Ensure a <= c for consistency (swap if needed)
  3. Call check function with appropriate parameters
  4. 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 Evaluator

Example 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" and t = "cdab"

Step 2: Transform Query Indices

  • Original query: [0, 1, 4, 5] means we can rearrange s[0:1] and s[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") and t[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:

  1. 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)

  2. Determine case: Since b=1 < c=2, we have non-overlapping intervals.

  3. 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] vs count(pre2, 0, 1) = [0,0,1,1] ✗

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 and pre2: We iterate through m = n/2 characters, and for each character, we copy the previous prefix array which takes O(|Σ|) time. This gives us O(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 |Σ|, taking O(|Σ|) time.
    • The sub function also operates on arrays of size |Σ|, taking O(|Σ|) time.
    • The check function calls count and sub a constant number of times, resulting in O(|Σ|) time per query.
    • Total for all queries: O(q × |Σ|)
  • 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 and pre2: Each contains (m + 1) arrays of size 26, where m = n/2. This gives us 2 × (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 and d_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], use prefix[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)
Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Tailor Your Study Plan:

What's the output of running the following function using input 56?

1KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12def letter_combinations_of_phone_number(digits):
13    def dfs(path, res):
14        if len(path) == len(digits):
15            res.append(''.join(path))
16            return
17
18        next_number = digits[len(path)]
19        for letter in KEYBOARD[next_number]:
20            path.append(letter)
21            dfs(path, res)
22            path.pop()
23
24    res = []
25    dfs([], res)
26    return res
27
1private static final Map<Character, char[]> KEYBOARD = Map.of(
2    '2', "abc".toCharArray(),
3    '3', "def".toCharArray(),
4    '4', "ghi".toCharArray(),
5    '5', "jkl".toCharArray(),
6    '6', "mno".toCharArray(),
7    '7', "pqrs".toCharArray(),
8    '8', "tuv".toCharArray(),
9    '9', "wxyz".toCharArray()
10);
11
12public static List<String> letterCombinationsOfPhoneNumber(String digits) {
13    List<String> res = new ArrayList<>();
14    dfs(new StringBuilder(), res, digits.toCharArray());
15    return res;
16}
17
18private static void dfs(StringBuilder path, List<String> res, char[] digits) {
19    if (path.length() == digits.length) {
20        res.add(path.toString());
21        return;
22    }
23    char next_digit = digits[path.length()];
24    for (char letter : KEYBOARD.get(next_digit)) {
25        path.append(letter);
26        dfs(path, res, digits);
27        path.deleteCharAt(path.length() - 1);
28    }
29}
30
1const KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12function letter_combinations_of_phone_number(digits) {
13    let res = [];
14    dfs(digits, [], res);
15    return res;
16}
17
18function dfs(digits, path, res) {
19    if (path.length === digits.length) {
20        res.push(path.join(''));
21        return;
22    }
23    let next_number = digits.charAt(path.length);
24    for (let letter of KEYBOARD[next_number]) {
25        path.push(letter);
26        dfs(digits, path, res);
27        path.pop();
28    }
29}
30

Recommended Readings

Prefix Sum

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: The Smart, Data-Driven Way to Prepare for Tech Interviews

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 Review

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!

Load More