2983. Palindrome Rearrangement Queries
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:
- We ensure that the prefix and suffix of
sandtaround our intervals are already matching; if they are not, forming a palindrome is impossible. - 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.
- If our intervals are separate, the strings between them must be equal, and inside the intervals, they must have the same characters.
- 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.
Which data structure is used in a depth first search?
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.
-
String Split and Reverse: We start by splitting our string into two parts: the first half
sand the reversed second halft. This allows us to deal with matching characters in a palindrome directly across the two halves. -
Prefix Sum Arrays: We then create prefix sum arrays
pre1forsandpre2fort. These arrays have an additional dimension for the 26 lowercase letters ('a' to 'z'). Thus,pre1[i][j]andpre2[i][j]will count the number of occurrences of thej-th letter up to thei-th character insandt, respectively. -
Differences Array: Along with the prefix sum arrays, we build an array
diffthat records the difference count betweensandtat each position.diff[i]represents how many characters in the prefix ending atiare different betweensandt. -
Query Handling: Now, we handle each query by first converting the
c_iandd_iof the queries sincetis the reversed second half. This conversion ensures we are comparing the correct intervals. -
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 makesandtidentical, and hence it cannot form a palindrome. - If one interval is entirely inside the other, we check if the characters within this interval of
sandtare 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.
- If the prefix or the suffix outside the given intervals has any differences, as recorded in
-
Subtraction Helper Function: A helper function
subis 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. -
Returning Results: Finally, we walk through each query, perform the necessary checks based on the above case analysis, and append
TrueorFalseto 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.
Which of the following is a min heap? 
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
671import 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}
961#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};
991function 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}
95Which one best describes the time complexity of the following code?
1int factorial(int n) {
2 if (n < 0) {
3 return -1;
4 } else if (n == 0) {
5 return 1;
6 } else {
7 return n * factorial(n - 1);
8 }
9}
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.
What is the running time of the following code?
1int sqrt(int n) { 2 for (int guess = 1; guess * guess <= n; guess++) { 3 if (guess * guess == n) { 4 return guess; 5 } 6 } 7 return -1; 8}
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
Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture
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 algomonster s3 us east 2 amazonaws com recursion jpg You first
Got a question? Ask the Teaching 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.