#1177

Medium

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Can Make Palindrome from Substring

Given a string and queries, determine if a substring can be rearranged and modified to form a palindrome.

array hash table string bit manipulation prefix sum

Problem Statement

You are given a string s and an array of queries, where each query is a tuple [left, right, k]. For each query, the substring s[left...right] can be rearranged, and you can replace up to k characters within that substring with any lowercase letter. Your task is to determine if this substring can be rearranged and modified to become a palindrome.

Return an array where each element represents the result of a corresponding query. A value of true means it is possible to make the substring a palindrome, and false otherwise.

Examples

Example 1

Input: s = "abcda", queries = [[3,3,0],[1,2,0],[0,3,1],[0,3,2],[0,4,1]]

Output: [true,false,false,true,true]

queries[0]: substring = "d", is palidrome. queries[1]: substring = "bc", is not palidrome. queries[2]: substring = "abcd", is not palidrome after replacing only 1 character. queries[3]: substring = "abcd", could be changed to "abba" which is palidrome. Also this can be changed to "baab" first rearrange it "bacd" then replace "cd" with "ab". queries[4]: substring = "abcda", could be changed to "abcba" which is palidrome.

Example 2

Input: s = "lyb", queries = [[0,1,0],[2,2,1]]

Output: [false,true]

Example details omitted.

Constraints

1 <= s.length, queries.length <= 105
0 <= lefti <= righti < s.length
0 <= ki <= s.length
s consists of lowercase English letters.

Solution Approach

Character Frequency Analysis

Since the substring can be rearranged, we can focus on the frequency of characters. For a substring to be rearranged into a palindrome, all characters must occur an even number of times, except for at most one character (which can appear an odd number of times). Using a hash table or frequency count can efficiently track the characters.

Using Prefix Frequency Arrays

One efficient approach is to compute a prefix frequency array for the string s, where each entry stores the frequency of each character up to that index. This allows for fast lookup of the frequency of characters in any substring by simply subtracting the relevant indices of the prefix array.

Handling Modifications

For each query, after determining the frequency of characters in the substring, check how many characters have odd frequencies. If the number of odd frequencies is less than or equal to k, it's possible to adjust the substring to form a palindrome by replacing characters. If not, it's impossible.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity depends on the approach used for counting frequencies and processing the queries. With prefix frequency arrays, each query can be processed in constant time after an initial preprocessing step, leading to a total time complexity of O(n + q), where n is the length of the string and q is the number of queries. The space complexity is O(n), mainly due to the storage of the frequency prefix array.

What Interviewers Usually Probe

Assess if the candidate understands the importance of character frequency in palindrome problems.
Look for familiarity with efficient substring processing techniques, such as prefix sums or sliding windows.
Evaluate if the candidate can optimize the solution for large inputs, given the constraints.

Common Pitfalls or Variants

Common pitfalls

Failing to account for character frequencies correctly, especially the condition that at most one character can have an odd frequency.
Not considering the effect of k properly, which could allow for a substring to become a palindrome if enough modifications are allowed.
Overcomplicating the solution with unnecessary string operations or incorrect handling of indices when counting character frequencies.

Follow-up variants

Extending the problem to handle substrings with multiple occurrences of a character beyond a single odd count.
Optimizing for different kinds of queries, such as range queries with multiple modifications allowed.
Changing the constraint to allow replacements only within a fixed subset of characters, not any lowercase English letter.

FAQ

What is the main technique to solve the Can Make Palindrome from Substring problem?

The main technique involves character frequency analysis. You only need to consider the frequencies of characters in the substring and check if, after rearrangement and up to k modifications, the substring can become a palindrome.

How do I efficiently calculate character frequencies in a substring?

You can use a prefix frequency array to quickly compute the frequency of characters in any substring by subtracting the relevant indices of the prefix array.

What are the constraints of the problem?

The string s and the number of queries can each be as large as 105, and the length of the substring to consider for each query can vary from 0 to the length of s.

Can the solution handle large inputs?

Yes, the solution can handle large inputs efficiently if it uses prefix sums and processes each query in constant time after preprocessing.

What does 'k' represent in the problem?

'k' is the maximum number of character replacements allowed in the substring to potentially form a palindrome. If the number of odd character frequencies is less than or equal to k, the substring can be rearranged and modified to be a palindrome.

terminal

Solution

Solution 1: Prefix Sum

First, consider whether a substring can become a palindrome after at most $k$ replacements. Obviously, we need to count the number of times each character appears in the substring, which can be implemented through prefix sum. For characters that appear an even number of times, we do not need to replace them. For characters that appear an odd number of times, we need to replace them. The number of replacements is $\lfloor \frac{x}{2} \rfloor$, where $x$ is the number of characters that appear an odd number of times. If $\lfloor \frac{x}{2} \rfloor \leq k$, then this substring can become a palindrome.

1

2

3

4

5

6

7

8

9

10

11

12

class Solution:
    def canMakePaliQueries(self, s: str, queries: List[List[int]]) -> List[bool]:
        n = len(s)
        ss = [[0] * 26 for _ in range(n + 1)]
        for i, c in enumerate(s, 1):
            ss[i] = ss[i - 1][:]
            ss[i][ord(c) - ord("a")] += 1
        ans = []
        for l, r, k in queries:
            cnt = sum((ss[r + 1][j] - ss[l][j]) & 1 for j in range(26))
            ans.append(cnt // 2 <= k)
        return ans

Continue Practicing

#1178 number of valid words for each puzzle #1371 find the longest substring containing vowels in even counts #1442 count triplets that can form two arrays of equal xor