博客
关于我
【Lintcode】1246. Longest Repeating Character Replacement
阅读量:195 次
发布时间:2019-02-28

本文共 1036 字,大约阅读时间需要 3 分钟。

双指针法是解决这个问题的高效方法。通过维护一个区间[j, i],并用count数组记录区间内每个字母的出现次数。当区间内的字符总数减去出现次数最多的字母的出现次数大于k时,右移左指针j,直到满足条件。每次满足条件时,更新最长子串的长度。

思路解析

  • 双指针维护区间:使用左右两个指针j和i来确定当前的区间[j, i]。j从左向右移动,i从左向右扩展。
  • 记录字母出现次数:使用count数组记录区间内每个字母的出现次数。
  • 检查条件:当区间内的总字符数减去出现次数最多的字母的次数大于k时,右移j,直到满足条件。
  • 更新最长子串长度:每次满足条件时,计算区间长度并更新最大值。

代码解析

public class Solution {
public int characterReplacement(String s, int k) {
int[] count = new int[26];
int res = 0;
for (int i = 0, j = 0; i < s.length(); i++) {
count[s.charAt(i) - 'A']++;
while (!check(count, k)) {
count[s.charAt(j) - 'A']--;
j++;
}
res = Math.max(res, i - j + 1);
}
return res;
}
private boolean check(int[] count, int k) {
int sum = 0, max = 0;
for (int i : count) {
sum += i;
max = Math.max(max, i);
}
return sum - max <= k;
}
}

时间复杂度

  • O(n):每个字符只被处理一次,时间复杂度为O(n)。
  • 空间复杂度:使用了一个固定大小的数组count,空间复杂度为O(1)。

这个方法高效且简洁,能够在O(n)的时间内解决问题,适用于长字符串。

转载地址:http://xkjs.baihongyu.com/

你可能感兴趣的文章
nghttp3使用指南
查看>>
Nginx
查看>>
nginx + etcd 动态负载均衡实践(三)—— 基于nginx-upsync-module实现
查看>>
nginx + etcd 动态负载均衡实践(二)—— 组件安装
查看>>
nginx + etcd 动态负载均衡实践(四)—— 基于confd实现
查看>>
Nginx + Spring Boot 实现负载均衡
查看>>
Nginx + uWSGI + Flask + Vhost
查看>>
Nginx - Header详解
查看>>
Nginx - 反向代理、负载均衡、动静分离、底层原理(案例实战分析)
查看>>
nginx 1.24.0 安装nginx最新稳定版
查看>>
nginx 301 永久重定向
查看>>
nginx css,js合并插件,淘宝nginx合并js,css插件
查看>>
Nginx gateway集群和动态网关
查看>>
Nginx Location配置总结
查看>>
Nginx log文件写入失败?log文件权限设置问题
查看>>
Nginx Lua install
查看>>
nginx net::ERR_ABORTED 403 (Forbidden)
查看>>
Nginx SSL私有证书自签,且反代80端口
查看>>
Nginx upstream性能优化
查看>>
Nginx 中解决跨域问题
查看>>