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.

#1177

Medium

auto_awesome数组·哈希·扫描

LeetCode 题解工作台

构建回文串检测

给你一个字符串 s ，请你对 s 的子串进行检测。每次检测，待检子串都可以表示为 queries[i] = [left, right, k] 。我们可以重新排列子串 s[left], ..., s[right] ，并从中选择最多 k 项替换成任何小写英文字母。如果在上述检测过程中，子串可以…

数组哈希表字符串位运算前缀和

题目描述

给你一个字符串 s，请你对 s 的子串进行检测。

每次检测，待检子串都可以表示为 queries[i] = [left, right, k]。我们可以 重新排列 子串 s[left], ..., s[right]，并从中选择最多 k 项替换成任何小写英文字母。

如果在上述检测过程中，子串可以变成回文形式的字符串，那么检测结果为 true，否则结果为 false。

返回答案数组 answer[]，其中 answer[i] 是第 i 个待检子串 queries[i] 的检测结果。

注意：在替换时，子串中的每个字母都必须作为 独立的 项进行计数，也就是说，如果 s[left..right] = "aaa" 且 k = 2，我们只能替换其中的两个字母。（另外，任何检测都不会修改原始字符串 s，可以认为每次检测都是独立的）

示例：

输入：s = "abcda", queries = [[3,3,0],[1,2,0],[0,3,1],[0,3,2],[0,4,1]]
输出：[true,false,false,true,true]
解释：
queries[0] : 子串 = "d"，回文。
queries[1] : 子串 = "bc"，不是回文。
queries[2] : 子串 = "abcd"，只替换 1 个字符是变不成回文串的。
queries[3] : 子串 = "abcd"，可以变成回文的 "abba"。 也可以变成 "baab"，先重新排序变成 "bacd"，然后把 "cd" 替换为 "ab"。
queries[4] : 子串 = "abcda"，可以变成回文的 "abcba"。

提示：

1 <= s.length, queries.length <= 10^5
0 <= queries[i][0] <= queries[i][1] < s.length
0 <= queries[i][2] <= s.length
s 中只有小写英文字母

lightbulb

解题思路

方法一：前缀和

我们先考虑一个子串能否在经过最多 $k$ 次替换后变成回文串，显然，我们需要统计子串中每个字符出现的次数，这可以通过前缀和来实现。对于出现偶数次的字符，我们不需要进行替换，对于出现奇数次的字符，我们需要进行替换，替换的次数为 $\lfloor \frac{x}{2} \rfloor$ ，其中 $x$ 为出现奇数次的字符的个数。如果 $\lfloor \frac{x}{2} \rfloor \leq k$ ，那么这个子串就可以变成回文串。

因此，我们定义一个前缀和数组 $ss$ ，其中 $ss[i][j]$ 表示字符串 $s$ 的前 $i$ 个字符中，字符 $j$ 出现的次数。那么对于一个子串 $s[l..r]$ ，我们可以通过 $ss[r + 1][j] - ss[l][j]$ 得到子串中字符 $j$ 出现的次数。我们遍历所有的查询，对于每个查询 $[l, r, k]$ ，我们统计子串 $s[l..r]$ 中出现奇数次的字符的个数 $x$ ，如果 $\lfloor \frac{x}{2} \rfloor \leq k$ ，那么这个子串就可以变成回文串。

时间复杂度 $O((n + m) \times C)$ ，空间复杂度 $O(n \times C)$ ，其中 $n$ 和 $m$ 分别为字符串 $s$ 和查询数组的长度；而 $C$ 为字符集的大小，本题中字符集为小写英文字母，因此 $C = 26$ 。

1

2

3

4

5

6

7

8

9

10

11

12

13

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

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

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

warning

常见陷阱

外企场景

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

swap_horiz

进阶变体

外企场景

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

help

常见问题

外企场景

继续练习

#1178 猜字谜 #1371 每个元音包含偶数次的最长子字符串 #1442 形成两个异或相等数组的三元组数目