当前位置:网站首页>424. The longest repeated character after replacement ●●
424. The longest repeated character after replacement ●●
2022-07-05 23:24:00 【chenyfan_】
424. The longest repeated character after replacement ●●
describe
Give you a string s And an integer k . You can select any character in the string , And change it to any other Capitalization English characters . This operation can be performed up to k Time .
After doing this , return The length of the longest substring containing the same letter .
Example
Input :s = “AABABBA”, k = 1
Output :4
explain :
Will the middle one ’A’ Replace with ’B’, The string changes to “AABBBBA”.
Substring “BBBB” There is the longest repeating letter , The answer for 4.
Answer key
1. Double pointer 1
Use a one-dimensional array to store the occurrence times of each letter in the window , Each time, the letters on the left border are used as fixed letters ( That is, replace different letters with this letter ), The right pointer moves to the right one by one , When it can no longer be replaced , Move the left pointer to the right , And update the current fixed letter ;
Be careful , Because this solution takes the left boundary letter as the fixed letter every time , So we also need to consider the length of the letter before the left boundary after it is replaced ,
such as s = “ACBBB”,k = 2; The correct result is 5; If you don't consider front , The result is 3.
class Solution {
public:
int characterReplacement(string s, int k) {
vector<int> cnts(26, 0);
int n = s.length(), ans = 0;
int l = 0, rest = k;
cnts[s[0]-'A'] = 1; // Initial left border
for(int r = 1; r < n; ++r){
if(s[r] != s[l]) --rest; // Replace operation ,--rest
++cnts[s[r]-'A']; // Statistics frequency
while(rest < 0){
// Replacement failed
--cnts[s[l]-'A'];
++l; // Move the left pointer
rest = k - ((r-l+1) - cnts[s[l]-'A'])); // Update the fixed letter to the left border letter ,(r-l+1)-cnts[s[l]-'A'] Indicates the number of letters to be replaced in the current window
}
int front = min(rest, l); // Consider replacing the previous letter
ans = max(ans, r-l+1+front); // Update Max
}
return ans;
}
};
2. Double pointer 2
Enumerate each position in the string as the right endpoint , Then find the location of its farthest left endpoint , Satisfy the interval except The type of characters that appear most often outside , The remaining characters ( That is, non longest repeating character ) No more than k individual .
So we can think of using double pointers to maintain these intervals , Every time the right pointer moves right , If the interval still satisfies the condition , So the left pointer doesn't move , Otherwise, the left pointer can be moved one space to the right at most , Guarantee The interval length does not decrease ( Remain unchanged or increase ).
Although such operation will cause some intervals not to meet the conditions , That is, after moving the left pointer , The non longest repeating character in this interval exceeds k individual (maxSame Changed but may not be updated ).
But such a range is also unlikely to contribute to the answer ( Until you move the right pointer to a letter that appears more frequently ). When we move the right pointer to the end , The length of the interval corresponding to the left and right pointers must correspond to the interval with the largest length .
Every time the interval moves right , We update the number of times the character shifted right appears , Then try to use it to update the historical maximum number of repeated characters , Finally, we use the maximum to calculate the number of non longest repeating characters in the interval , In order to judge whether the left pointer needs to move right .
class Solution {
public:
int characterReplacement(string s, int k) {
vector<int> cnts(26, 0);
int n = s.length();
int l = 0, r = 0, maxSame = 0;
for(; r < n; ++r){
++cnts[s[r]-'A'];
maxSame = max(maxSame, cnts[s[r]-'A']); // Maximum update frequency , Only when it occurs more frequently
if(k < (r-l+1) - maxSame){
// Replacement failed
--cnts[s[l]-'A']; // Move the left pointer , contract the window ( The maximum total length does not change at this time )
++l;
}
} // for In circulation r Take one more step , At the end r = n
return r-l; // The window size is guaranteed not to decrease , The maximum eligible window length
}
};
边栏推荐
- (4)UART应用设计及仿真验证2 —— TX模块设计(无状态机)
- C Primer Plus Chapter 9 question 10 binary conversion
- 【经典控制理论】自控实验总结
- Multi camera stereo calibration
- Live tiktok shop 2022 latest gameplay card slot overseas live e-commerce new traffic
- 数据库基础知识(面试)
- Calculating the number of daffodils in C language
- 698. 划分为k个相等的子集 ●●
- 3:第一章:认识JVM规范2:JVM规范,简介;
- Detailed explanation of pointer and array written test of C language
猜你喜欢
Non rigid / flexible point cloud ICP registration
Practice of concurrent search
开关电源Buck电路CCM及DCM工作模式
February 13, 2022-4-symmetric binary tree
两数之和、三数之和(排序+双指针)
Three.JS VR看房
Expectation, variance and covariance
2: Chapter 1: understanding JVM specification 1: introduction to JVM;
芯源&立创EDA训练营——无刷电机驱动
Getting started stm32--gpio (running lantern) (nanny level)
随机推荐
grafana工具界面显示报错influxDB Error
Live tiktok shop 2022 latest gameplay card slot overseas live e-commerce new traffic
Registration of Electrical Engineering (elementary) examination in 2022 and the latest analysis of Electrical Engineering (elementary)
Shell: operator
Expectation, variance and covariance
Non rigid / flexible point cloud ICP registration
Go语言实现原理——锁实现原理
Comparison between webgl and webgpu [3] - vertex buffer
TypeError: this. getOptions is not a function
Multi camera stereo calibration
(4) UART application design and simulation verification 2 - RX module design (stateless machine)
视频标准二三事
Selenium+pytest automated test framework practice
VS2010编写动态链接库DLL和单元测试,转让DLL测试的正确性
带外和带内的区别
Multi sensor fusion of imu/ electronic compass / wheel encoder (Kalman filter)
Three.js-01 入门
White hat talks about web security after reading 2
判断二叉树是否为完全二叉树
基于脉冲神经网络的物体检测