1177. Can Make Palindrome from Substring

MediumBit ManipulationArrayHash TableStringPrefix Sum
Leetcode Link

Problem Description

The problem requires us to determine whether a substring of a given string s can be rearranged and possibly modified by replacing up to k letters to form a palindrome. This needs to be done for a series of queries, each represented by a triplet [left, right, k]. Specifically, for each query, we are allowed to:

  1. Rearrange the substring s[left...right].
  2. Replace up to k letters in the substring with any other lowercase English letter.

If the substring can be made into a palindrome using the above operations, the result for that query is true; otherwise, it is false. We are to return an array of boolean values representing the result for each query.

A palindrome is a string that reads the same forward and backward. For a string to be a palindrome, each character must have a matching pair except for at most one character, which can be in the middle of the palindrome if the string length is odd.

Intuition

The intuition behind the solution approach is to first understand the characteristics of a palindrome. For a string to be a palindrome, each character except for at most one must occur an even number of times (they can be mirrored around the center of the string).

Given this, we can reformulate the problem as: At most how many characters in the target substring have an odd number of occurrences, and whether this number can be reduced to at most one with at most k character replacements.

To efficiently compute the number of characters with odd occurrences in any given substring, the solution employs prefix sums. Specifically, it calculates the count of each character of the alphabet up to each position in the string. This provides a quick way to determine the counts of each letter in any substring.

Here's the step-by-step approach of the solution:

  1. Create a list ss to keep track of the prefix sums – the count of each character up to each index of the string.
  2. Iterate over the string s to fill up the ss list with the counts.
  3. For each query, use the ss list to calculate the number of characters with an odd count in the target substring.
  4. Check if the half of the number of odd-count characters is less than or equal to k, since each pair of odd-count characters can be replaced by any other character to make them even.
  5. For each query, append the result (true or false) to the answer list ans.
  6. Return the ans list as output once all queries are processed.

This approach allows us to efficiently answer each query without having to directly manipulate the substring, reducing the problem to a question of counting occurrences which can be solved in constant time for each query.

Learn more about Prefix Sum patterns.

Solution Approach

The solution uses the concept of prefix sums and bitwise operations to solve the problem efficiently. Here's how it works, with reference to the key steps in the Python code implementation:

  1. Initialization: A two-dimensional list ss is initiated where ss[i][j] represents the count of the j-th letter (where a is 0, b is 1, and so on) up to the i-th position in the string s. This list is initialized with n + 1 rows and 26 columns (since there are 26 letters in the English alphabet) filled initially with zeros. This extra row is for handling the prefix sum from the beginning of the string.

    1ss = [[0] * 26 for _ in range(n + 1)]
  2. Populating Prefix Sums: As we iterate through the string s, a temporary copy of the previous row of the ss list is made, and then the count of the current character is updated by incrementing the corresponding counter.

    1for i, c in enumerate(s, 1):
    2    ss[i] = ss[i - 1][:]
    3    ss[i][ord(c) - ord("a")] += 1
  3. Processing Queries: For each query [l, r, k], we calculate the number of characters with an odd number of occurrences within the substring s[l...r]. This is done by using the corresponding prefix sums to find the total count of each letter in the substring and then applying a bitwise AND operation with 1 (which is equivalent to checking if the count is odd).

    1cnt = sum((ss[r + 1][j] - ss[l][j]) & 1 for j in range(26))

    The above line calculates the difference between the counts at the position after the end of the substring (r + 1) and at the start of the substring (l). This difference gives us the count of each character in the substring. We then check if this count is odd by using the bitwise AND operation with 1.

  4. Checking for Palindrome Potential: The number of odd-count characters that need to be paired off (which requires replacement) is cnt // 2. We check if this number is less than or equal to k, which signifies whether we can turn the substring into a palindrome through k or fewer character replacements.

    1ans.append(cnt // 2 <= k)

    This check is appended to our result list ans.

  5. Returning Results: Once all queries are processed, the list ans containing the result of each query is returned.

    1return ans

The use of prefix sums allows for a quick calculation of character occurrences within any given substring in O(1) time, after an O(n) preprocessing phase. The overall complexity of the solution is O(n + q), where n is the length of the string and q is the number of queries, making it highly efficient for the problem at hand.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's consider the string s = "aabbcc" and queries queries = [[0,5,2], [1,4,1]].

Initialization with Prefix Sums: We first initialize our ss list with extra space to handle cases when the substring starts at index 0. The initialized ss list looks like this initially (considering a simplified alphabet of three letters for this illustration):

1ss = [[0, 0, 0],  // before the first character ('a')
2      [0, 0, 0],  // before the second character ('a') and so on
3      [0, 0, 0],
4      [0, 0, 0],
5      [0, 0, 0],
6      [0, 0, 0],
7      [0, 0, 0]]  // after the last character ('c')

Populating Prefix Sums: After populating the ss list with the prefix sums of each character, the list reflects the following (the -th index in the inner lists corresponds to the alphabetically j-th character):

1ss = [[0, 0, 0],  // before 'a'
2      [1, 0, 0],  // before 'a'
3      [2, 0, 0],  // before 'b'
4      [2, 1, 0],  // before 'b'
5      [2, 2, 0],  // before 'c'
6      [2, 2, 1],  // before 'c'
7      [2, 2, 2]]  // after 'c'

Query 1: [0, 5, 2] We need to check the substring s[0...5] which is "aabbcc". For this substring, the counts of each character are 2 a's, 2 b's, and 2 c's. The count of odd-occurring characters cnt is therefore 0. We don't need any replacements to make a palindrome, so the result for this query is true.

Query 2: [1, 4, 1] This time, we're looking at the substring s[1...4] which is "abbc". Here, the count of each character is 1 a, 2 bs, and 1 c. Therefore, we have cnt=2 characters occurring an odd number of times ("a" and "c"). We need 1 replacement to make either "a" or "c" match the other character (e.g., change "c" to "a" to form "abba"). Since we are allowed to replace up to k=1 characters, the result for this query is true.

Answer: Thus, the array of boolean values representing the result for each query is [true, true].

Solution Implementation

1class Solution:
2    def canMakePaliQueries(self, s: str, queries: List[List[int]]) -> List[bool]:
3        # Calculate the length of the string.
4        string_length = len(s)
5      
6        # Initialize a prefix sum array where each element is a list representing the count of letters up to that index.
7        prefix_sum = [[0] * 26 for _ in range(string_length + 1)]
8      
9        # Populate the prefix sum matrix with the counts of each character.
10        for index, char in enumerate(s, 1):
11            prefix_sum[index] = prefix_sum[index - 1][:]
12            prefix_sum[index][ord(char) - ord("a")] += 1
13      
14        # Initialize a list to store the answers for the queries.
15        answers = []
16      
17        # Process each query in the list of queries.
18        for start, end, max_replacements in queries:
19            # Calculate the count of odd occurrences of each letter in the range [start, end].
20            odd_count = sum((prefix_sum[end + 1][j] - prefix_sum[start][j]) & 1 for j in range(26))
21          
22            # A palindrome can be formed if the half of odd_count is less than or equal to the allowed max_replacements.
23            can_form_palindrome = odd_count // 2 <= max_replacements
24          
25            # Add the result for the current query to the answers list.
26            answers.append(can_form_palindrome)
27      
28        # Return the answers list containing results for all queries.
29        return answers
30
1class Solution {
2    public List<Boolean> canMakePaliQueries(String s, int[][] queries) {
3        int stringLength = s.length();
4        // Prefix sum array to keep count of characters up to the ith position
5        int[][] charCountPrefixSum = new int[stringLength + 1][26];
6      
7        // Fill the prefix sum array with character counts
8        for (int i = 1; i <= stringLength; ++i) {
9            // Copy the counts from previous index
10            for (int j = 0; j < 26; ++j) {
11                charCountPrefixSum[i][j] = charCountPrefixSum[i - 1][j];
12            }
13            // Increment the count of the current character
14            charCountPrefixSum[i][s.charAt(i - 1) - 'a']++;
15        }
16      
17        // List to store results of queries
18        List<Boolean> results = new ArrayList<>();
19      
20        // Process each query
21        for (int[] query : queries) {
22            int left = query[0], right = query[1], maxReplacements = query[2];
23            int oddCount = 0;
24          
25            // Compute the count of characters with odd occurrences in the
26            // substring [left, right]
27            for (int j = 0; j < 26; ++j) {
28                oddCount += (charCountPrefixSum[right + 1][j] - charCountPrefixSum[left][j]) & 1;
29            }
30          
31            // Add true if half of the oddCount is less than or equal to allowed replacements (maxReplacements)
32            results.add(oddCount / 2 <= maxReplacements);
33        }
34      
35        // Return the list containing results of queries
36        return results;
37    }
38}
39
1#include <vector>
2#include <cstring>
3using namespace std;
4
5class Solution {
6public:
7    vector<bool> canMakePaliQueries(string s, vector<vector<int>>& queries) {
8        int n = s.size();
9        // Create a 2D array to keep track of character frequency up to each position in the string
10        int charCountPrefixSum[n + 1][26];
11        memset(charCountPrefixSum, 0, sizeof(charCountPrefixSum)); // Initialize the array with 0
12
13        // Populate the prefix sum array with character frequency counts
14        for (int i = 1; i <= n; ++i) {
15            for (int j = 0; j < 26; ++j) {
16                charCountPrefixSum[i][j] = charCountPrefixSum[i - 1][j];
17            }
18            charCountPrefixSum[i][s[i - 1] - 'a']++;
19        }
20
21        vector<bool> answers; // This will store the answers for each query
22
23        // Go through each query to check for palindrome possibility
24        for (auto& query : queries) {
25            int left = query[0], right = query[1], maxReplacements = query[2];
26            int oddCount = 0; // Variable to track the count of characters appearing odd number of times
27
28            // Count how many characters appear an odd number of times within the query's range
29            for (int j = 0; j < 26; ++j) {
30                oddCount += (charCountPrefixSum[right + 1][j] - charCountPrefixSum[left][j]) & 1;
31            }
32
33            // A palindrome can be formed if the half of the odd count is less than or equal to allowed replacements
34            answers.emplace_back(oddCount / 2 <= maxReplacements);
35        }
36
37        return answers; // Return the final answers for all queries
38    }
39};
40
1function canMakePaliQueries(s: string, queries: number[][]): boolean[] {
2    const lengthOfString = s.length;
3    const charCountPrefixSum: number[][] = Array(lengthOfString + 1)
4        .fill(0)
5        .map(() => Array(26).fill(0)); // Array to store the prefix sum of character counts
6
7    // Calculate the prefix sum of character counts
8    for (let i = 1; i <= lengthOfString; ++i) {
9        charCountPrefixSum[i] = charCountPrefixSum[i - 1].slice(); // Copy previous count
10        ++charCountPrefixSum[i][s.charCodeAt(i - 1) - 'a'.charCodeAt(0)]; // Increment count of current character
11    }
12
13    const result: boolean[] = [];
14    // Process each query
15    for (const [left, right, maxReplacements] of queries) {
16        let oddCount = 0; // Count of characters that appear an odd number of times
17
18        // Calculate the number of characters with an odd count in the substring
19        for (let j = 0; j < 26; ++j) {
20            oddCount += (charCountPrefixSum[right + 1][j] - charCountPrefixSum[left][j]) & 1;
21        }
22
23        // Push true if half of the odd count is less than or equal to k, otherwise false.
24        result.push((oddCount >> 1) <= maxReplacements);
25    }
26
27    return result; // Return the array of boolean results for each query
28}
29

Time and Space Complexity

The given Python code provides a solution for determining if a substring of the input string s can be rearranged to form a palindrome with at most k replacements. The computation of this solution involves pre-computing the frequency of each character in the alphabet at each index of the string s, and then using that information to answer each query.

Time Complexity:

  1. Building the prefix sum array ss takes O(n * 26) time, where n is the length of the string s, since we iterate over the string and for each character, we copy the previous counts and update the count of one character.
  2. Answering each query involves calculating the difference in character counts between the right and left indices for each of the 26 letters, which is O(26). This is done for each query. If there are q queries, this part of the algorithm takes O(q * 26) time.
  3. The total time complexity is therefore O(n * 26 + q * 26) which simplifies to O(n + q) when multiplied by the constant 26 factor for the alphabet size.

Hence, the time complexity is O(n + q).

Space Complexity:

  1. The prefix sum array ss uses O(n * 26) space to store the count of characters up to each index in the string s.
  2. The space for the answer list is O(q), where q is the number of queries.
  3. As such, the total space complexity is the sum of the space for the prefix sum array and the space for the answer list, which is O(n * 26 + q).

Thus, the space complexity is O(n * 26 + q) which can be approximated to O(n) since the size of the alphabet is constant.

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


Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:
Question 1 out of 10

Which of the following is a good use case for backtracking?


Recommended Readings