当前位置:网站首页>LeetCode_ Sliding window_ Medium_ 395. Longest substring with at least k repeated characters
LeetCode_ Sliding window_ Medium_ 395. Longest substring with at least k repeated characters
2022-07-02 15:15:00 【I'm up and down in the Jianghu】
1. subject
Give you a string s And an integer k , Please find out s Longest substring in , The number of occurrences of each character in the substring shall not be less than k . Returns the length of this substring .
Example 1:
Input :s = “aaabb”, k = 3
Output :3
explain : The longest string is “aaa” , among ‘a’ repeated 3 Time .
Example 2:
Input :s = “ababbc”, k = 2
Output :5
explain : The longest string is “ababb” , among ‘a’ repeated 2 Time , ‘b’ repeated 3 Time .
Tips :
1 <= s.length <= 104
s It's only made up of lowercase letters
1 <= k <= 105
source : Power button (LeetCode)
link :https://leetcode.cn/problems/longest-substring-with-at-least-k-repeating-characters
2. Ideas
(1) The law of violent exhaustion
This method is easy to think of , Namely Traversal string s All lengths of are greater than or equal to k The string of , Judge the number of occurrences of each character in them , And use res Record the length of the longest substring that meets the conditions , After traversal, return res that will do , In the judgment process, you can use a hash table to store the number of occurrences of each string . But the time complexity of this method is high , stay LeetCode Submit on will appear “ Time limit exceeded ” A hint of .
(2) The sliding window
Train of thought reference Official solution to this problem .
3. Code implementation (Java)
// Ideas 1———— The law of violent exhaustion
class Solution {
public int longestSubstring(String s, int k) {
// key / value : character / Corresponding number of occurrences
HashMap<Character, Integer> hashMap = new HashMap<>();
int length = s.length();
int res = 0;
for (int i = 0; i < length; i++) {
for (int j = i + k; j <= length; j++) {
// Get substring
String subStr = s.substring(i, j);
boolean flag = true;
hashMap.clear();
for (int l = 0; l < subStr.length(); l++) {
char c = subStr.charAt(l);
hashMap.put(c, hashMap.getOrDefault(c, 0) + 1);
}
for (int cnt : hashMap.values()) {
if (cnt < k) {
flag = false;
break;
}
}
if (flag == true) {
res = Math.max(res, subStr.length());
}
}
}
return res;
}
}
// Ideas 2———— The sliding window
class Solution {
public static int longestSubstring(String s, int k) {
int res = 0;
int length = s.length();
for (int i = 1; i <= 26; i++) {
int left = 0;
int right = 0;
int[] cnt = new int[26];
int total = 0;
int less = 0;
while (right < length) {
cnt[s.charAt(right) - 'a']++;
if (cnt[s.charAt(right) - 'a'] == 1) {
total++;
less++;
}
if (cnt[s.charAt(right) - 'a'] == k) {
less--;
}
while (total > i) {
cnt[s.charAt(left) - 'a']--;
if (cnt[s.charAt(left) - 'a'] == k - 1) {
less++;
}
if (cnt[s.charAt(left) - 'a'] == 0) {
total--;
less--;
}
left++;
}
if (less == 0) {
res = Math.max(res , right - left + 1);
}
right++;
}
}
return res;
}
}
边栏推荐
猜你喜欢
LeetCode - 搜索二维矩阵
18_Redis_Redis主从复制&&集群搭建
实用调试技巧
03_线性表_链表
[C language] explain the initial and advanced levels of the pointer and points for attention (1)
15_Redis_Redis.conf详解
N皇后问题的解决
[development environment] install the visual studio community 2013 development environment (download the installation package of visual studio community 2013 with update 5 version)
07_ Hash
forEach的错误用法,你都学废了吗
随机推荐
记一次面试
Base64 编码原来还可以这么理解
Application and practice of Jenkins pipeline
C语言实现N皇后问题
Why can't programmers who can only program become excellent developers?
Printf function and scanf function in C language
蜻蜓低代码安全工具平台开发之路
Implementation of n queen in C language
[noi simulation] Elis (greedy, simulation)
解决el-radio-group 回显后不能编辑问题
C RichTextBox controls the maximum number of lines displayed
广州市应急管理局发布7月高温高湿化工安全提醒
学习使用php实现公历农历转换的方法代码
18_Redis_Redis主从复制&&集群搭建
SQL 后计算的利器 SPL
【NOI模拟赛】伊莉斯elis(贪心,模拟)
为什么只会编程的程序员无法成为优秀的开发者?
06_栈和队列转换
如何对 TiDB 进行 TPC-C 测试
Mfc a dialog calls B dialog function and passes parameters