网站前期运营策略,郑州公司网站建设服务,设计色彩的门户网站模板,系统优化的知识给你一个字符串 s#xff0c;请你对 s 的子串进行检测。
每次检测#xff0c;待检子串都可以表示为 queries[i] [left, right, k]。我们可以 重新排列 子串 s[left], …, s[right]#xff0c;并从中选择 最多 k 项替换成任何小写英文字母。
如果在上述检测过程中#xf…给你一个字符串 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”。
代码
class Solution {int[][] t;public ListBoolean canMakePaliQueries(String s, int[][] queries) {int ns.length();ListBoolean resnew ArrayList();tnew int[n1][26];for (int i1;in;i)//字符个数的前缀和{int curs.charAt(i-1)-a;t[i]t[i-1].clone();t[i][cur];}for(int[] c:queries)res.add(getCanMakePaliQueries(s,c[0],c[1])c[2]);return res;}public int getCanMakePaliQueries(String s, int l,int r) {
//统计区间内组成回文需要改变的字符个数int res0;int[] helpernew int[26];for(int i0;i26;i){int ct[r1][i]-t[l][i];if(c%21)res;}return res/2;}
}
