2983. Palindrome Rearrangement Queries

HardHash TableStringPrefix Sum
Leetcode Link

Problem Description

The problem presents us with a string s that has an even length n and a list of queries. Each query is a list [a_i, b_i, c_i, d_i]. The indices in a query split the string s into four sections with the goal of rearranging characters within two certain substrings of s to potentially form a palindrome. A palindrome is a word or phrase that reads the same backward as forward.

The first half of the string (from index 0 to n/2 - 1) can be rearranged within the interval [a_i, b_i], and the second half (from n/2 to n - 1) can be rearranged within the interval [c_i, d_i]. An important note is that these intervals are 0-indexed and inclusive.

For every query, we have to decide if it's possible to rearrange the characters within the specified intervals to make the string s a palindrome. Each query is independent of the others, which means that the original string s is reset before considering each new query. The outcome for each query is a boolean value indicating whether the palindrome can be created, so our final answer is a list of boolean values corresponding to each query.

Intuition

The intuition behind solving this problem lies in understanding that to make a palindrome, each character from the first half of the string has to have a corresponding matching character in the reversed second half. If we consider the first half of the string s and the reversed second half of the string s (let's call it t), and when looking at any particular query [a_i, b_i, c_i, d_i], we are actually trying to see if the characters within s[a_i, b_i] can match the characters in t[c_i, d_i] after potentially rearranging them.

To efficiently handle the queries related to character counts in substrings, we preprocess the string s and t to build prefix sum arrays that help us quickly determine the character frequency up to any given index. With these prefix sums, we can calculate the frequency count of characters within any given interval.

We also calculate the differences array diff, which captures the number of distinct characters between s and t at each prefix. This array will be crucial in determining if portions of s and t that are not included in our query's intervals already mismatch and thus make it impossible to form a palindrome.

When looking at each query:

  1. We ensure that the prefix and suffix of s and t around our intervals are already matching; if they are not, forming a palindrome is impossible.
  2. If one interval is completely within the other in our split string, then the substring within that interval must contain the same characters for a palindrome to be possible.
  3. If our intervals are separate, the strings between them must be equal, and inside the intervals, they must have the same characters.
  4. If the intervals overlap, the excess characters in one interval must match the deficiency in the other for the two halves to be rearranged into a palindrome.

With these cases, we can iterate through each query, using our prefix sums and diff array, to determine the possibility of forming a palindrome for each one.

Learn more about Prefix Sum patterns.

Solution Approach

In the given solution, we approach the problem by considering the following steps, which apply preprocessing and efficient computation to handle queries effectively.

  1. String Split and Reverse: We start by splitting our string into two parts: the first half s and the reversed second half t. This allows us to deal with matching characters in a palindrome directly across the two halves.

  2. Prefix Sum Arrays: We then create prefix sum arrays pre1 for s and pre2 for t. These arrays have an additional dimension for the 26 lowercase letters ('a' to 'z'). Thus, pre1[i][j] and pre2[i][j] will count the number of occurrences of the j-th letter up to the i-th character in s and t, respectively.

  3. Differences Array: Along with the prefix sum arrays, we build an array diff that records the difference count between s and t at each position. diff[i] represents how many characters in the prefix ending at i are different between s and t.

  4. Query Handling: Now, we handle each query by first converting the c_i and d_i of the queries since t is the reversed second half. This conversion ensures we are comparing the correct intervals.

  5. Case Analysis: After setup, for each query, we consider different cases depending on the relation between the segments [a_i, b_i] and [c_i, d_i]:

    • If the prefix or the suffix outside the given intervals has any differences, as recorded in diff, it is impossible to make s and t identical, and hence it cannot form a palindrome.
    • If one interval is entirely inside the other, we check if the characters within this interval of s and t are the same.
    • If intervals are separate, we check if the strings between them are already matching and if inside the intervals the characters can be matched.
    • If the intervals overlap, we subtract the characters in the overlapping parts from each other to see if the mismatch can be resolved.
  6. Subtraction Helper Function: A helper function sub is used for subtracting character counts represented in the prefix sum arrays in the case of overlapping intervals. This function essentially computes the characters that are in excess in one interval and need to be matched by characters in the other interval.

  7. Returning Results: Finally, we walk through each query, perform the necessary checks based on the above case analysis, and append True or False to the answer list depending on whether it's possible to re-order the characters to form a palindrome.

The use of prefix sum arrays allows us to compute character counts in constant time after the preprocessing, and the diff array enables us to quickly determine if non-queried sections of s and t are going to prevent a palindrome formation. By considering the four main cases of interval relationships, we cover all possible configurations of the input intervals and assess the feasibility of palindrome formation for each query.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

How does quick sort divide the problem into subproblems?

Example Walkthrough

To illustrate the solution approach, let's go through a small example.

Let's say our input string 's' is "mnooppqq" which has an even length of 8, and we're given a single query [1, 3, 5, 7]. Based on the query, our goal is to determine if we can rearrange s[1:3] which is "no" and s[5:7] which is "qq" to make the string a palindrome.

Step 1: String Split and Reverse

We split 's' into two halves: s_front = "mnoo" and s_back = "ppqq", then reverse the second half to get t = "qqpp".

Step 2: Prefix Sum Arrays

We construct prefix sum arrays pre1 for s_front and pre2 for t. For simplicity, let's say we consider the character 'm', 'n', 'o', 'p', and 'q' only, we would have something like:

1s_front:    m n o o  |  Count of characters up to index:
2pre1:    n  |   m  |   n  |   o  |   p  |   q
3          -------------------------
4index 0  |   1  |   0  |   0  |   0  |   0  |    m = 1
5index 1  |   1  |   1  |   0  |   0  |   0  |    m = 1, n = 1
6index 2  |   1  |   1  |   1  |   0  |   0  |    m = 1, n = 1, o = 1
7index 3  |   1  |   1  |   2  |   0  |   0  |    m = 1, n = 1, o = 2
8
9t (reversed s_back): q q p p |  Count of characters:
10pre2:    n  |   m  |   n  |   o  |   p  |   q
11          -------------------------
12index 0  |   0  |   0  |   0  |   0  |   1  |    q = 1
13index 1  |   0  |   0  |   0  |   0  |   2  |    q = 2
14index 2  |   0  |   0  |   0  |   1  |   2  |    p = 1, q = 2
15index 3  |   0  |   0  |   0  |   2  |   2  |    p = 2, q = 2

Step 3: Differences Array diff

The differences array diff is constructed by comparing s_front and t at each prefix:

1m n o o
2q q p p
3diff:  1 2 2 2

Step 4: Query Handling

For the query [1, 3, 5, 7], we first note that in 't', these indices correspond to [2, 0] because t is reversed, so our intervals in s and t actually are: s[1, 3] -> "no" and t[0, 2] -> "qqp".

Step 5: Case Analysis

  • Since diff[0] is not zero, it indicates there are character mismatches in the prefix (outside our query range), which would make it impossible to form a palindrome.

Step 7: Returning Results

Based on the analysis, we determine that this particular query cannot be satisfied because of the mismatched characters outside the interval of the query. So our result for this query is False. The final answer list will be [False].

This example shows how the provided solution approach can quickly assess the possibility of forming a palindrome for a given query by efficiently using preprocessing (prefix sum arrays and differences array) and considering different interval relations.

Solution Implementation

1from typing import List
2
3class Solution:
4    def canMakePalindromeQueries(self, s: str, queries: List[List[int]]) -> List[bool]:
5      
6        # Helper function to calculate the frequency difference between two prefixes
7        def get_prefix_count_diff(prefix_counts: List[List[int]], i: int, j: int) -> List[int]:
8            return [x - y for x, y in zip(prefix_counts[j + 1], prefix_counts[i])]
9
10        # Helper function to subtract the frequency counts of one string from another
11        def subtract_counts(count1: List[int], count2: List[int]) -> List[int]:
12            result = []
13            for x, y in zip(count1, count2):
14                if x - y < 0:
15                    return []  # Return an empty list to signify invalid case
16                result.append(x - y)
17            return result
18      
19        # Main function to check if a substring is a palindrome
20        # by comparing prefix frequency counts, considering offsets and positions
21        def is_palindrome_possible(prefix1: List[List[int]], prefix2: List[List[int]], 
22                                   start1: int, end1: int, start2: int, end2: int) -> bool:
23            if diff[start1] > 0 or diff[mid] - diff[max(end1, end2) + 1] > 0:
24                return False
25          
26            if end2 <= end1:
27                # Case when second substring lies inside the first substring
28                return get_prefix_count_diff(prefix1, start1, end1) == get_prefix_count_diff(prefix2, start1, end1)
29          
30            if end1 < start2:
31                # Case when the two substrings are non-overlapping
32                return (diff[start2] - diff[end1 + 1] == 0 and
33                        get_prefix_count_diff(prefix1, start1, end1) == get_prefix_count_diff(prefix2, start1, end1) and
34                        get_prefix_count_diff(prefix1, start2, end2) == get_prefix_count_diff(prefix2, start2, end2))
35          
36            # Overlapping substrings
37            counts1 = subtract_counts(get_prefix_count_diff(prefix1, start1, end1), get_prefix_count_diff(prefix2, start1, start2 - 1))
38            counts2 = subtract_counts(get_prefix_count_diff(prefix2, start2, end2), get_prefix_count_diff(prefix1, end1 + 1, end2))
39            return counts1 and counts2 and counts1 == counts2
40
41        # Preprocess strings to obtain frequency of each character at each prefix
42        n = len(s)
43        mid = n // 2
44        s_rev = s[mid:][::-1]
45        s = s[:mid]
46        prefix1 = [[0] * 26 for _ in range(mid + 1)]
47        prefix2 = [[0] * 26 for _ in range(mid + 1)]
48        diff = [0] * (mid + 1)
49      
50        for i, (ch1, ch2) in enumerate(zip(s, s_rev), 1):
51            prefix1[i] = prefix1[i - 1][:]
52            prefix2[i] = prefix2[i - 1][:]
53            prefix1[i][ord(ch1) - ord("a")] += 1
54            prefix2[i][ord(ch2) - ord("a")] += 1
55            diff[i] = diff[i - 1] + int(ch1 != ch2)
56      
57        # Process each query to determine if the substring can be a palindrome
58        results = []
59        for start1, end1, start2, end2 in queries:
60            start2, end2 = n - 1 - end2, n - 1 - start2
61            is_possible = (is_palindrome_possible(prefix1, prefix2, start1, end1, start2, end2)
62                           if start1 <= start2
63                           else is_palindrome_possible(prefix2, prefix1, start2, end2, start1, end1))
64            results.append(is_possible)
65      
66        return results
67
1import java.util.Arrays;
2
3class Solution {
4
5    // Function to check if substrings can be rearranged to make palindromes based on the queries
6    public boolean[] canMakePalindromeQueries(String s, int[][] queries) {
7        int n = s.length();
8        int halfLength = n / 2;
9        // Reverse the second half of the string
10        String reversedHalf = new StringBuilder(s.substring(halfLength)).reverse().toString();
11        // Take the first half of the string
12        s = s.substring(0, halfLength);
13        // Create prefix sum arrays for character counts in the halves
14        int[][] prefixFirstHalf = new int[halfLength + 1][26];
15        int[][] prefixSecondHalf = new int[halfLength + 1][26];
16        // Array to store count of differing characters at each position
17        int[] diffCount = new int[halfLength + 1];
18
19        // Initialize prefix sum arrays
20        prefixFirstHalf[0] = new int[26];
21        prefixSecondHalf[0] = new int[26];
22      
23        // Calculate the prefix sums and the diffCount
24        for (int i = 1; i <= halfLength; ++i) {
25            prefixFirstHalf[i] = prefixFirstHalf[i - 1].clone();
26            prefixSecondHalf[i] = prefixSecondHalf[i - 1].clone();
27            // Increment count of the current character in the prefix sum arrays
28            ++prefixFirstHalf[i][s.charAt(i - 1) - 'a'];
29            ++prefixSecondHalf[i][reversedHalf.charAt(i - 1) - 'a'];
30            // Increment the diffCount if characters at the same position are different
31            diffCount[i] = diffCount[i - 1] + (s.charAt(i - 1) != reversedHalf.charAt(i - 1) ? 1 : 0);
32        }
33
34        // Result array to store outcomes of queries
35        boolean[] results = new boolean[queries.length];
36
37        // Process each query
38        for (int i = 0; i < queries.length; ++i) {
39            int[] query = queries[i];
40            int leftIndex = query[0], rightIndex = query[1];
41            int leftReversedIndex = n - 1 - query[3], rightReversedIndex = n - 1 - query[2];
42            // Depending on the indices, call the check function with appropriate arguments
43            results[i] = leftIndex <= leftReversedIndex ? 
44                         check(prefixFirstHalf, prefixSecondHalf, diffCount, leftIndex, rightIndex, leftReversedIndex, rightReversedIndex) :
45                         check(prefixSecondHalf, prefixFirstHalf, diffCount, leftReversedIndex, rightReversedIndex, leftIndex, rightIndex);
46        }
47
48        return results;
49    }
50
51    // Helper method to check if a query's substring can be rearranged to make a palindrome
52    private boolean check(int[][] prefixFirstHalf, int[][] prefixSecondHalf, int[] diffCount, 
53                          int leftIndex, int rightIndex, int leftReversedIndex, int rightReversedIndex) {
54        // Check for the presence of differing characters outside the specified range
55        if (diffCount[leftIndex] > 0 || diffCount[diffCount.length - 1] - diffCount[Math.max(rightIndex, rightReversedIndex) + 1] > 0) {
56            return false;
57        }
58        // For overlapping ranges, compare character counts directly
59        if (rightReversedIndex <= rightIndex) {
60            return Arrays.equals(count(prefixFirstHalf, leftIndex, rightIndex), count(prefixSecondHalf, leftIndex, rightIndex));
61        }
62        // Check for non-overlapping and adjacent ranges
63        if (rightIndex < leftReversedIndex) {
64            return diffCount[leftReversedIndex] - diffCount[rightIndex + 1] == 0 &&
65                   Arrays.equals(count(prefixFirstHalf, leftIndex, rightIndex), count(prefixSecondHalf, leftIndex, rightIndex)) &&
66                   Arrays.equals(count(prefixFirstHalf, leftReversedIndex, rightReversedIndex), count(prefixSecondHalf, leftReversedIndex, rightReversedIndex));
67        }
68        // Calculate counts for overlapping ranges and compare
69        int[] count1 = subtractCounts(count(prefixFirstHalf, leftIndex, rightIndex), count(prefixSecondHalf, leftIndex, leftReversedIndex - 1));
70        int[] count2 = subtractCounts(count(prefixSecondHalf, leftReversedIndex, rightReversedIndex), count(prefixFirstHalf, rightIndex + 1, rightReversedIndex));
71        return count1 != null && count2 != null && Arrays.equals(count1, count2);
72    }
73
74    // Helper method to count characters using the prefix arrays
75    private int[] count(int[][] prefix, int startIndex, int endIndex) {
76        int[] charCount = new int[26];
77        for (int i = 0; i < 26; ++i) {
78            charCount[i] = prefix[endIndex + 1][i] - prefix[startIndex][i];
79        }
80        return charCount;
81    }
82
83    // Helper method to subtract character counts
84    private int[] subtractCounts(int[] count1, int[] count2) {
85        int[] resultCount = new int[26];
86        for (int i = 0; i < 26; ++i) {
87            resultCount[i] = count1[i] - count2[i];
88            // If result is negative, return null as it means the substring can't be made into a palindrome
89            if (resultCount[i] < 0) {
90                return null;
91            }
92        }
93        return resultCount;
94    }
95}
96
1#include <vector>
2#include <string>
3#include <algorithm>
4
5class Solution {
6public:
7    std::vector<bool> canMakePalindromeQueries(std::string s, std::vector<std::vector<int>>& queries) {
8        int n = s.length();
9        int middle = n / 2;
10      
11        // Split string s into two halves and reverse the second half
12        std::string firstHalf = std::string(s.begin(), s.begin() + middle);
13        std::string secondHalf = std::string(s.begin() + middle, s.end());
14        std::reverse(secondHalf.begin(), secondHalf.end());
15      
16        // Precompute prefix counts for the characters in both halves
17        std::vector<std::vector<int>> prefixCountsFirstHalf(middle + 1, std::vector<int>(26));
18        std::vector<std::vector<int>> prefixCountsSecondHalf(middle + 1, std::vector<int>(26));
19      
20        // Precompute the differences between the halves
21        std::vector<int> differences(middle + 1, 0);
22
23        for (int i = 1; i <= middle; ++i) {
24            prefixCountsFirstHalf[i] = prefixCountsFirstHalf[i - 1];
25            prefixCountsSecondHalf[i] = prefixCountsSecondHalf[i - 1];
26          
27            ++prefixCountsFirstHalf[i][firstHalf[i - 1] - 'a'];
28            ++prefixCountsSecondHalf[i][secondHalf[i - 1] - 'a'];
29          
30            differences[i] = differences[i - 1] + (firstHalf[i - 1] == secondHalf[i - 1] ? 0 : 1);
31        }
32
33        // Check palindrome possibility for each query
34        std::vector<bool> result(queries.size(), false);
35        for (size_t i = 0; i < queries.size(); ++i) {
36            std::vector<int>& q = queries[i];
37            int leftIndex = q[0], rightIndex = q[1];
38            int comparisonLeftIndex = n - 1 - q[3];
39            int comparisonRightIndex = n - 1 - q[2];
40          
41            result[i] = (leftIndex <= comparisonLeftIndex) ? 
42                            check(prefixCountsFirstHalf, prefixCountsSecondHalf, differences, leftIndex, rightIndex, comparisonLeftIndex, comparisonRightIndex) : 
43                            check(prefixCountsSecondHalf, prefixCountsFirstHalf, differences, comparisonLeftIndex, comparisonRightIndex, leftIndex, rightIndex);
44        }
45        return result;
46    }
47
48private:
49    // Helper method to check if palindrome can be made with given prefix counts, differences, and indexes
50    bool check(const std::vector<std::vector<int>>& prefixCountsFirst, const std::vector<std::vector<int>>& prefixCountsSecond, const std::vector<int>& differences, int startFirst, int endFirst, int startSecond, int endSecond) {
51        if (differences[startFirst] > 0 || differences[differences.size() - 1] - differences[std::max(endFirst, endSecond) + 1] > 0) {
52            return false;
53        }
54      
55        if (endSecond <= endFirst) {
56            return countsEqual(prefixCountsFirst, startFirst, endFirst, prefixCountsSecond, startFirst, endFirst);
57        }
58      
59        if (endFirst < startSecond) {
60            return differences[startSecond] - differences[endFirst + 1] == 0 && 
61                   countsEqual(prefixCountsFirst, startFirst, endFirst, prefixCountsSecond, startFirst, endFirst) && 
62                   countsEqual(prefixCountsFirst, startSecond, endSecond, prefixCountsSecond, startSecond, endSecond);
63        }
64      
65        std::vector<int> countDiffFirst = subtractCounts(count(prefixCountsFirst, startFirst, endFirst), count(prefixCountsSecond, startFirst, startSecond - 1));
66        std::vector<int> countDiffSecond = subtractCounts(count(prefixCountsSecond, startSecond, endSecond), count(prefixCountsFirst, endFirst + 1, endSecond));
67      
68        return !countDiffFirst.empty() && !countDiffSecond.empty() && countDiffFirst == countDiffSecond;
69    }
70
71    // Helper method to calculate count difference between two character counts
72    std::vector<int> count(const std::vector<std::vector<int>>& prefixCounts, int start, int end) {
73        std::vector<int> charCount(26);
74        for (int i = 0; i < 26; ++i) {
75            charCount[i] = prefixCounts[end + 1][i] - prefixCounts[start][i];
76        }
77        return charCount;
78    }
79
80    // Helper method to subtract one character count array from another
81    std::vector<int> subtractCounts(const std::vector<int>& count1, const std::vector<int>& count2) {
82        std::vector<int> charCount(26);
83        for (int i = 0; i < 26; ++i) {
84            charCount[i] = count1[i] - count2[i];
85            if (charCount[i] < 0) {
86                return std::vector<int>(); // If any value is negative, return an empty vector
87            }
88        }
89        return charCount;
90    }
91
92    // Helper method that checks if two counts are equal
93    bool countsEqual(const std::vector<std::vector<int>>& prefixCountsFirst, int a, int b, const std::vector<std::vector<int>>& prefixCountsSecond, int c, int d) {
94        std::vector<int> countFirst = count(prefixCountsFirst, a, b);
95        std::vector<int> countSecond = count(prefixCountsSecond, c, d);
96        return countFirst == countSecond;
97    }
98};
99
1function canMakePalindromeQueries(s: string, queries: number[][]): boolean[] {
2    const halfLength: number = s.length >> 1; // Calculate the half-length of the string
3    const t: string = s.slice(halfLength).split('').reverse().join(''); // Reverse second half of the string
4    s = s.slice(0, halfLength); // s is now the first half of the original string
5
6    // Initialize prefix sum arrays for the first half and the reversed second half of the string
7    const prefixSumFirstHalf: number[][] = Array.from({ length: halfLength + 1 }, () => Array(26).fill(0));
8    const prefixSumSecondHalf: number[][] = Array.from({ length: halfLength + 1 }, () => Array(26).fill(0));
9    const differences: number[] = Array(halfLength + 1).fill(0); // Array to store the differences
10
11    // Calculate the prefix sums and the differences between first and second halves
12    for (let i = 1; i <= halfLength; ++i) {
13        prefixSumFirstHalf[i] = [...prefixSumFirstHalf[i - 1]];
14        prefixSumSecondHalf[i] = [...prefixSumSecondHalf[i - 1]];
15        ++prefixSumFirstHalf[i][s.charCodeAt(i - 1) - 'a'.charCodeAt(0)];
16        ++prefixSumSecondHalf[i][t.charCodeAt(i - 1) - 'a'.charCodeAt(0)];
17        differences[i] = differences[i - 1] + (s[i - 1] === t[i - 1] ? 0 : 1);
18    }
19
20    const answers: boolean[] = Array(queries.length).fill(false); // Initialize the answer array
21    // Iterate through each query and fill the answer array
22    for (let i = 0; i < queries.length; ++i) {
23        const [start, end, startRev, endRev] = queries[i];
24        const reversedStart = s.length - 1 - endRev;
25        const reversedEnd = s.length - 1 - startRev;
26        answers[i] = start <= reversedStart
27            ? check(prefixSumFirstHalf, prefixSumSecondHalf, differences, start, end, reversedStart, reversedEnd)
28            : check(prefixSumSecondHalf, prefixSumFirstHalf, differences, reversedStart, reversedEnd, start, end);
29    }
30    return answers; // Return the answer array
31}
32
33// Helper method to check whether a substring can be permuted to a palindrome
34function check(
35    prefixSumFirst: number[][],
36    prefixSumSecond: number[][],
37    differences: number[],
38    start: number,
39    end: number,
40    reversedStart: number,
41    reversedEnd: number,
42): boolean {
43    if (differences[start] > 0 || differences[differences.length - 1] - differences[Math.max(end, reversedEnd) + 1] > 0) {
44        return false;
45    }
46
47    if (reversedEnd <= end) {
48        return arraysEqual(countChars(prefixSumFirst, start, end), countChars(prefixSumSecond, start, end));
49    }
50
51    if (end < reversedStart) {
52        return (
53            differences[reversedStart] - differences[end + 1] === 0 &&
54            arraysEqual(countChars(prefixSumFirst, start, end), countChars(prefixSumSecond, start, end)) &&
55            arraysEqual(countChars(prefixSumFirst, reversedStart, reversedEnd), countChars(prefixSumSecond, reversedStart, reversedEnd))
56        );
57    }
58
59    const countFirst: number[] | null = subtract(countChars(prefixSumFirst, start, end), countChars(prefixSumSecond, start, reversedStart - 1));
60    const countSecond: number[] | null = subtract(countChars(prefixSumSecond, reversedStart, reversedEnd), countChars(prefixSumFirst, end + 1, reversedEnd));
61
62    return countFirst !== null && countSecond !== null && arraysEqual(countFirst, countSecond);
63}
64
65// Helper method to count occurrences of characters in a substring using prefix sums
66function countChars(prefixSum: number[][], startIndex: number, endIndex: number): number[] {
67    const charCount: number[] = new Array(26).fill(0);
68    for (let i = 0; i < 26; ++i) {
69        charCount[i] = prefixSum[endIndex + 1][i] - prefixSum[startIndex][i];
70    }
71    return charCount;
72}
73
74// Helper method to subtract two character count arrays
75function subtract(charCount1: number[], charCount2: number[]): number[] | null {
76    const result: number[] = new Array(26).fill(0);
77    for (let i = 0; i < 26; ++i) {
78        result[i] = charCount1[i] - charCount2[i];
79        if (result[i] < 0) {
80            return null; // If any character count is negative, return null
81        }
82    }
83    return result;
84}
85
86// Helper method to check if two arrays are equal
87function arraysEqual(arr1: number[], arr2: number[]): boolean {
88    for (let i = 0; i < arr1.length; i++) {
89        if (arr1[i] !== arr2[i]) {
90            return false;
91        }
92    }
93    return true;
94}
95

Time and Space Complexity

The time complexity of the code is O((n + q) * |Σ|), where n is the length of the string s and q is the number of queries in the array queries. The character set |Σ| represents the size of the character set, which, in this case, is the set of lowercase English letters, thus |Σ| is equal to 26. The complexity arises because for each character in the string and each query, we perform a constant amount of work relative to the size of the alphabet.

The space complexity of the code is O(n * |Σ|). This is due to the storage requirements for the prefix sum arrays pre1 and pre2, each of which requires space for all character counts up to the midpoint of the string, and thus together they occupy space proportional to 2 * (n/2) * |Σ|, which simplifies to n * |Σ|.

Learn more about how to find time and space complexity quickly using problem constraints.


Fast Track Your Learning with Our Quick Skills Quiz:

What is the worst case running time for finding an element in a binary search tree(not necessarily balanced) of size n?


Recommended Readings


Got a question? Ask the Monster Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


🪄