Leetcode 424.替换后的最长重复字符

Stella981
• 阅读 317

替换后的最长重复字符

给你一个仅由大写英文字母组成的字符串,你可以将任意位置上的字符替换成另外的字符,总共可最多替换 k 次。在执行上述操作后,找到包含重复字母的最长子串的长度。

注意:
字符串长度 和 k 不会超过 104。

示例 1:

输入:

s = "ABAB", k = 2

输出:

4

解释:

用两个'A'替换为两个'B',反之亦然。

示例 2:

输入:

s = "AABABBA", k = 1

输出:

4

解释:

将中间的一个'A'替换为'B',字符串变为 "AABBBBA"。

子串 "BBBB" 有最长重复字母, 答案为 4。

思路:

题目的意思比较清楚,不过可能的情况有很多,不可能用代码去寻找最佳的替换位置,所以这里采用一种滑动窗口的方法。

定义start和end两个标记,中间的内容即是窗口,计算窗口内所有字母出现的次数,因为全是大写字母,所以可以用一个26位的数组来记录窗口内每个字母出现的次数。

找到窗口内出现最多的次数,加上允许替换的字母数k,看是否超过窗口宽度,如果超过了,说明窗口还可以更长, 也就是说窗口内重复的字母的长度可以更长,就将end右移一位,形成新的窗口,然后继续重复上面的步骤。如果没超过,说明能构成的最长的重复字母长度已经到顶了,这时应该将start右移一位,来寻找新的可能的更长重复字母长度。

每次计算重复字母长度时,当出现更长的可能时,都更新最终的结果。

为了减少时间复杂度,我们不去每次都遍历窗口来计算出现的字母次数,而是在移动end或者start时,将对应位置的字母的次数加一或者减一。

要注意各种边界条件是什么。

 1 public class Solution {
 2     public int characterReplacement(String s, int k) {
 3         if (s.length() < 1) return 0;
 4         int start = 0;
 5         int end = 0;
 6         int res = 0;
 7         int[] charNum = new int[26];
 8         charNum[s.charAt(0) - 'A']++;
 9         while (s.length() > end) {
10             int maxChar = 0;
11             for (int i = 0; i < 26; i++) {
12                 if (charNum[i] > maxChar)
13                     maxChar = charNum[i];
14             }
15             if (maxChar + k > end - start) {
16                 end++;
17                 if (end < s.length())
18                     charNum[s.charAt(end) - 'A']++;
19             } else {
20                 charNum[s.charAt(start) - 'A']--;
21                 start++;
22             }
23             if (maxChar + k > res)
24                 res = maxChar + k <= s.length() ? maxChar + k : s.length();
25         }
26         return res;
27     }
28 }
点赞
收藏
评论区
推荐文章
一只编程熊 一只编程熊
3年前
【LeetCode每日一题 Day 5】5. 最长回文子串
大家好,我是编程熊,今天是LeetCode每日一题的第五天,一起学习LeetCode第五题《最长回文子串》。题意给你一个字符串s,找到s中最长的回文子串。示例txt输入:s"babad"输出:"bab"解释:"aba"同样是符合题意的答案。题解方法一采用简单暴力的方法,枚举每一个位置为单独回文中心(长度为奇数的子串,如aba)或者回文中心
Wesley13 Wesley13
2年前
java string 字符串替换
i、replace方法  该方法的作用是替换字符串中所有指定的字符,然后生成一个新的字符串。经过该方法调用以后,原来的字符串不发生改变。例如:     String s  “abcat”;     String s1  s.replace(‘a’,‘1’);  该代码的作用是将字符串s中所有的字符a替换成字符1,生成
DaLongggggg DaLongggggg
3年前
python百题大冲关-压缩字符串
挑战介绍实现一个算法来压缩一个字符串。压缩的要求如下:需要判断压缩能不能节省空间,仅在压缩后字符串比原字符串长度更短时进行压缩。压缩的格式是将连续相同字符替换为字符数字形式,例如"AAABCCDDDD"变为"A3BC2D4"。本次挑战中,你需要在compress_str.py文件中补充函数compress的空缺部分
Stella981 Stella981
2年前
Python 字符串常用方法 string
字符串操作  描述string.capitalize()将字符串的第一个字母大写string.count()    获得字符串中某个字符串的数目string.find()获得字符串中某一子字符串的起始位置,无则返回1string.isalnum()检测字符串是仅包含09AZazstring.isalpha()
Wesley13 Wesley13
2年前
MySQL常用函数
字符串函数concat(a,b,c,...)连接为一个字符串insert(str,x,y,instr)将字符串str从第x位置开始,y个字符长的子串替换为字符串instrLower(str)所有字符变为小写upper(str)所有字符变为大写
Stella981 Stella981
2年前
JavaScript算法系列之
1.输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba字符串拼接(先理解不输入重复字符的)1functionpermutate(str){2varresult;
Stella981 Stella981
2年前
LeetCode 459. 重复的子字符串(Repeated Substring Pattern)
459\.重复的子字符串459\.RepeatedSubstringPattern题目描述给定一个非空的字符串,判断它是否可以由它的一个子串重复多次构成。给定的字符串只含有小写英文字母,并且长度不超过10000。<spanclass"badgebadgepillbadgedanger"LeetCod
Wesley13 Wesley13
2年前
MySQL 数据类型
在MySQL中,有三种主要的类型:文本、数字和日期/时间类型。Text类型:数据类型描述备注CHAR(size)保存固定长度的字符串(可包含字母、数字以及特殊字符)。在括号中指定字符串的长度。最多255个字符。VARCHAR(size)保存可变长度的字符串(可包含字母、数字以及特殊字符)。在括号中指定字符串
Stella981 Stella981
2年前
LeetCode:(14. 最长公共前缀!!!!!)
题目:14\.最长公共前缀编写一个函数来查找字符串数组中的最长公共前缀。如果不存在公共前缀,返回空字符串“”。示例1:输入:\“flower”,“flow”,“flight”\输出:“fl”示例2:输入:\“dog”,“racecar”,“car”\输出:“”
Stella981 Stella981
2年前
LeetCode459. 重复的子字符串
1.问题描述给定一个非空的字符串,判断它是否可以由它的一个子串重复多次构成。给定的字符串只含有小写英文字母,并且长度不超过10000。示例1:输入:“abab”输出:True解释:可由子字符串“ab”重复两次构成。示例2:输入:“aba”输出:Fal