LeetCode 1156. Swap For Longest Repeated Character Substring
原题链接在这里:https://leetcode.com/problems/swap-for-longest-repeated-character-substring/
题目:
Given a string text
, we are allowed to swap two of the characters in the string. Find the length of the longest substring with repeated characters.
Example 1:
Input: text = "ababa"
Output: 3
Explanation: We can swap the first 'b' with the last 'a', or the last 'b' with the first 'a'. Then, the longest repeated character substring is "aaa", which its length is 3.
Example 2:
Input: text = "aaabaaa"
Output: 6
Explanation: Swap 'b' with the last 'a' (or the first 'a'), and we get longest repeated character substring "aaaaaa", which its length is 6.
Example 3:
Input: text = "aaabbaaa"
Output: 4
Example 4:
Input: text = "aaaaa"
Output: 5
Explanation: No need to swap, longest repeated character substring is "aaaaa", length is 5.
Example 5:
Input: text = "abcdef"
Output: 1
Constraints:
1 <= text.length <= 20000
text
consist of lowercase English characters only.
题解:
There could be 2 cases to achieve the fulfilled longest substring.
case 1: One block containing longest. And then replace one boundary char to be the same, and get len+1.
case 2: Two blocks containing same chars separated by 1 single different char. In this case, the single different char could be replaced.
Both cases, it needs to make sure that there are extra same chars.
Time Complexity: O(n). n = text.length.
Space: O(n).
AC Java:
class Solution {
public int maxRepOpt1(String text) {
if(text == null || text.length() == 0){
return 0;
} int len = text.length();
int [] map = new int[26];
List<Pair> groupsList = new ArrayList<>();
int i = 0; while(i < len){
char c = text.charAt(i);
int f = 0;
while(i < len && text.charAt(i) == c){
f++;
i++;
} groupsList.add(new Pair(c, f));
map[c-'a'] += f;
} int max = 0;
for(int j = 0; j<groupsList.size(); j++){
Pair cur = groupsList.get(j); // Single group
max = Math.max(max, Math.min(cur.f+1, map[cur.c - 'a'])); // Two groups
if(j < groupsList.size() - 2){
if(groupsList.get(j+1).f == 1 && cur.c == groupsList.get(j+2).c){
max = Math.max(max, Math.min(cur.f + groupsList.get(j+2).f + 1, map[cur.c - 'a']));
}
}
} return max;
}
} class Pair{
char c;
int f;
public Pair(char c, int f){
this.c = c;
this.f = f;
}
}
最新文章
- linux基础:第三关课前考试题整理
- Oracle 查看某表 被哪些表外键引用
- noi 6049 买书
- 输入 cc -c 指令出现问题
- VirtualBox共享文件夹等高级特性
- 59. Spiral Matrix II
- SPRING IN ACTION 第4版笔记-第六章RENDERING WEB VIEWS-006- 使用thymeleaf(TemplateResolver、SpringTemplateEngine、ThymeleafViewResolver、th:include、th:object、th:field=";*{firstName}";)
- 21、手把手教你Extjs5(二十一)模块Form的自定义的设计
- 基础知识:IDE集成开发环境(pycharm)、基本数据类型、用户的交互、运算符
- javaScript中的redirect
- Tomcat中配置URIEncoding=";UTF-8";来处理中文的方法
- mac 关于默认python2下的pip,和python3下pip 的坑
- CAN调度理论与实践分析
- ArcGIS API for javascript开发笔记(三)——解决打印输出的中文为乱码问题
- 功能强大的文件上传插件带上传进度-WebUploader
- yarn 用户导致的被挖矿 启用Kerberos认证功能,禁止匿名访问修改8088端口
- 【抽时间 试验】hibernate集合映射inverse和cascade详解
- python之numpy文件操作
- CSS去掉 a 标签点击后出现的虚线框
- Unity3D - 发布Android游戏