本文将介绍395.LongestSubstringwithAtLeastKRepeatingCharacters的详细情况，。我们将通过案例分析、数据研究等多种方式，帮助您更全面地了解这个主题，同时也
本文将介绍395. Longest Substring with At Least K Repeating Characters的详细情况，。我们将通过案例分析、数据研究等多种方式，帮助您更全面地了解这个主题，同时也将涉及一些关于003_LongestSubstringWithoutRepeatingCharacters、3. Longest Substring Without Repeating Characters、3_Longest Substring Without Repeating Characters -- LeetCode、JS算法——Longest Substring Without Repeating Characters的知识。
本文目录一览：- 395. Longest Substring with At Least K Repeating Characters
- 003_LongestSubstringWithoutRepeatingCharacters
- 3. Longest Substring Without Repeating Characters
- 3_Longest Substring Without Repeating Characters -- LeetCode
- JS算法——Longest Substring Without Repeating Characters
395. Longest Substring with At Least K Repeating Characters
原题链接
Find the length of the longest substring T of a given string (consists of lowercase letters only) such that every character in T appears no less than k times.
这题可以用分治法，递归实现。首先把整个字符串遍历一次，记录每个字符出现的次数。然后第二次遍历，目标是找出所有出现次数小于 k 的字符所在的位置，由于这些字符不可能出现在我们要找的子串中，所以可以把它们作为分割点，由此分割而得的子串再进行递归处理。
具体分割子串的方法：用 first、last 跟踪记录子串的开头和结尾，一开始两者都等于字符串的首位。如果当前字符出现次数大于等于 k，那么 last 移到当前字符的下一位置。如果当前字符出现次数小于 k，说明碰到了一个分割点，这是要判断由 first、last 标记的子串长度是否大于等于 k，是的话就递归处理这个子串，否则表明这个子串不可能包含重复 k 次的字符，忽略它。递归返回的结果要与当前的最大子串长度进行比较、更新。不论是否递归子串，碰到分割点时都要把 first 移到当前字符的后一位，表明上一个子串处理完毕，新的子串开始了。
根据我的算法，只有在碰到出现次数小于 k 的字符时才有可能触发子串递归，所以存在一种情况，就是字符串遍历到的最后一位是出现次数大于等于 k 的字符时，会遗漏掉一个从 first 开始一直延伸到字符串结尾的子串。因此遍历结束后要再进行一个额外的判断，如果 last-first>=k，那么这个子串也要递归；这种情况下还有更特殊的情况，就是 first 在整个遍历中都没有移动过，这说明整个字符串都是符合要求的。
class Solution {
public:
int longestSubstring(string s, int k) {
return helper(s, 0, s.size(), k);
}
int helper(string &s, int start, int end, int k) {
if(end-start<k) return 0;
int count[26] = {0};
int i;
int first=start, last=start;
int maxlen = 0;
for(i=start; i<end; i++) count[s[i]-''a'']++;
for(i=start; i<end; i++) {
if(count[s[i]-''a'']<k) {
if(last-first>=k) maxlen = max(maxlen, helper(s,first,last,k));
first = i+1;
}
else if(count[s[i]-''a'']>=k) {
last = i+1;
}
}
if(last-first>=k) {
if(first==start) maxlen = last-first;
else maxlen = max(maxlen, helper(s,first,last,k));
}
return maxlen;
}
};
第二种算法（这个不是我写的，但提供了不同思路）：two pointer
public int longestSubstring(String s, int k) {
int d = 0;
for (int numUniqueTarget = 1; numUniqueTarget <= 26; numUniqueTarget++)
d = Math.max(d, longestSubstringWithNUniqueChars(s, k, numUniqueTarget));
return d;
}
private int longestSubstringWithNUniqueChars(String s, int k, int numUniqueTarget) {
int[] map = new int[128];
int numUnique = 0; // counter 1
int numNoLessThanK = 0; // counter 2
int begin = 0, end = 0;
int d = 0;
while (end < s.length()) {
if (map[s.charAt(end)]++ == 0) numUnique++; // increment map[c] after this statement
if (map[s.charAt(end++)] == k) numNoLessThanK++; // inc end after this statement
while (numUnique > numUniqueTarget) {
if (map[s.charAt(begin)]-- == k) numNoLessThanK--; // decrement map[c] after this statement
if (map[s.charAt(begin++)] == 0) numUnique--; // inc begin after this statement
}
// if we found a string where the number of unique chars equals our target
// and all those chars are repeated at least K times then update max
if (numUnique == numUniqueTarget && numUnique == numNoLessThanK)
d = Math.max(end - begin, d);
}
return d;
}
所谓的两指针，也是用两个变量来维护子串的头和尾。但他的思路和我不同，不用分割字符串。由于我们不知道要找的子串中有多少种字符，可能值是从 1 到 26，所以我们可以遍历所有可能的字符种数。每一趟遍历都要把字符串从头到尾扫一遍，并且一边扫一边记录每个字符出现的次数，注意这个次数是指在子串中出现的次数，而不是整个字符串中的次数。numUnique 记录当前子串中的字符种数，numNoLessThanK 记录重复 k 次以上的字符种数。
例如在规定字符种数为 2 的遍历中，begin 和 end 标记子串的头尾，而且要确保这个字符串中只有两种字符。如果当前子串为 aabbb，下一个字符为 c，如果把 c 加入子串就超过种数限制了，所以要把 begin 前移，当子串变为 bbb 后，才可以把 c 加入。同时，每当子串中字符种数为 2，且所有字符都出现了至少 k 次（numUnique==numNoLessThanK），说明这可能是我们最终要找的子串，需要记录它的长度并更新最大值。
003_LongestSubstringWithoutRepeatingCharacters
/*** * * Given a string, find the length of the longest substring without repeating characters. * * Example 1: * * Input: "abcabcbb" * Output: 3 * Explanation: The answer is "abc", with the length of 3. * Example 2: * * Input: "bbbbb" * Output: 1 * Explanation: The answer is "b", with the length of 1. * Example 3: * * Input: "pwwkew" * Output: 3 * Explanation: The answer is "wke", with the length of 3. * Note that the answer must be a substring, "pwke" is a subsequence and not a substring. * * */
/*** * 关键： * 先遍历一遍放进hashmap，因此复杂度是O(n) * */
public class N003_LongestSubstringWithoutRepeatingCharacters {
/***
* 使用HashMap记录字符上次出现的位置
* 用pre记录最近重复字符出现的位置
* 则i(当前位置)-pre就是当前字符最长无重复字符的长度
* 取最大的就是字符串的最长无重复字符的长度
*
* 时间复杂度：O(n)
*/
public static int lengthOfLongestSubstring(String str) {
if (str == null || str.length() < 1)
return 0;
// 记录字符上次出现的位置
HashMap<Character, Integer> map = new HashMap<>();
int max = 0;
// 最近出现重复字符的位置
int pre = -1;
for (int i = 0, strLen = str.length(); i < strLen; i++) {
Character ch = str.charAt(i);
Integer index = map.get(ch);
if (index != null)
pre = Math.max(pre, index); //这一步很关键，取前一个相同字符位置，而不是后一个；后一个字符还有可能成为字串的元素
max = Math.max(max, i - pre);
map.put(ch, i);
}
return max;
}
public static void main(String args[]) {
String input = "nevereverbeacoder";
int len = lengthOfLongestSubstring(input);
System.out.println(len);
}
}
3. Longest Substring Without Repeating Characters
欢迎 fork and star：Nowcoder-Repository-github
3. Longest Substring Without Repeating Characters
题目
Given a string, find the length of the longest substring without repeating characters.
Examples:
Given "abcabcbb", the answer is "abc", which the length is 3.
Given "bbbbb", the answer is "b", with the length of 1.
Given "pwwkew", the answer is "wke", with the length of 3. Note that the answer must be a substring, "pwke" is a subsequence and not a substring.
解析
- solution 思路循序渐进，很值得思考！
- 对找到元素后更新位置处理，i 取 max (mp [s [j]] ,i) 细节处理。
class Solution_3 {
public:
int lengthOfLongestSubstring(string s) {
if (s.size()==0)
{
return 0;
}
int ret = 0;
map<char, int> mp;
int i = 0;
for (int j = 0; j < s.size();j++)
{
if (mp.count(s[j])) //找到了,没有插入当前元素，之前插入的相同元素充当当前元素,但要覆盖当前元素的位置second，//或者覆盖
{
ret = max(ret, j - i);
if (mp[s[j]]>=i) //有可能返回去 "abba"
{
i = mp[s[j]] + 1; //下次从第一次个重复的下一个位置开始
}
mp[s[j]] = j; //更新位置
}
else
{
mp.insert(make_pair(s[j],j));
}
}
ret = ret > (s.size() - i) ? ret : (s.size() - i); // 尾处理
return ret;
}
};
题目来源
- 3. Longest Substring Without Repeating Characters
- LeetCode(3) Longest Substring Without Repeating Characters
3_Longest Substring Without Repeating Characters -- LeetCode
C++解法一：
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int m[256] = {0},left = 0, res = 0;
for(int index = 0; index < s.size(); ++index)
{
if(m[s[index]] == 0|| m[s[index]] < left)
{
res = max(res,index-left+1);
}else{
left = m[s[index]];
}
m[s[index]] = index+1;
}
return res;
}
};算法解读：
1) 这里使用哈希的思想，把256个可能的字符都考虑在内，字符的ASCⅡ编码作为数组下标进行映射。如m[a]等价于m[97]。
2) res其实是result的缩写，表示返回的最大无重复子串的长度，left表示当前正在判断的子串的起始位置。
3) 进行一个for循环，当满足(m[s[i]] == 0 || m[s[i]] < left)条件时候，计算子串长度，并且与res比较最长并取之。
这里的m[s[i]]表示第i个字符上一次出现的位置，如果从来没有出现过即m[s[i]]==0, 则表示无重复；如果m[s[i]] < left
则表示上次出现的位置在当前判断的字串起始位置的左边，不重复。
否则，(m[s[i]] != 0 && m[s[i]] >= left),重复。此时要更新left的值为m[s[i]],即不left更新为当前字符与上一次重复
的字符位置的下一位 。这里的i+1 是因为i是从0开始的下标，而我们需要的是从1开始的序号。
4) i偏移都每一个字符都要几下当前的位置，即m[s[i]] = i + 1 。
C++解法二
复制代码
class Solution {
public:
int lengthOfLongestSubstring(string s) {
vector<int> m(256, -1);
int res = 0, left = -1;
for (int i = 0; i < s.size(); ++i) {
left = max(left, m[s[i]]);
m[s[i]] = i;
res = max(res, i - left);
}
return res;
}
};
算法分析：
1）与算法一思想一样，只是进行了精简。
2）每次循环，将left更新 max(left, m[s[i]])，如果s[i]在left的右边且
JS算法——Longest Substring Without Repeating Characters
算法描述：给定一个字符串，找到长度最大的无重复字符的子字符串，并输出其长度。
举例：输入字符串"abcabcbb"，结果是"abc"，length为3
输入字符串"bbbbb"，结果是"b"，length为1
输入字符串"pwwkew"，结果是"wke"，length为
第一时间想到的就是用循环来解决，通过两层循环找出所有不重复的组合，然后最后在这些组合里选出length值最大的字符串。
外层循环就是对每一个位置开始的子字符串都进行一次查找，比如输入的字符串是"abcdd",那么我们通过循环比对的字符串分别是:"abcdd","bcdd","cdd","dd","d"。
接下来我们就要对第一层循环取得的子字符串进行比对，从子字符串的第一位开始，每次向下移一位进行检查，直到遇到重复的字符串 为止，或者到末尾结束。
把所有得到的结果都push到一个数组里，然后对数组遍历找到length值最大的那个。
然后我们来看看代码实现：
var substrings=[];//用来存放所有的结果的数组
var next="";//用来临时存储字符串
var currentSubstring="";//每次外层循环都更新的子字符串
var max=0;//length最大值然后我们先检查传入字符串的长度，如果传入一个空字符，我们就直接返回0
//s是函数入口传入的参数
if(s.length){
//长度不为0开始处理
}else{
//长度为0则直接返回0
return 0;
}接下来我们对s进行处理：
for(var i=0;i<s.length;i++){
//利用substr截取每次内层要遍历的字符串，每次都向后移一位，所以直接传入i即可
currentSubstring=s.substr(i);
for(var j=0;j<s.length-i;j++){
//利用indexOf检查next中是否有重复，next初始为空字符串，所以第一个字符串肯定不会重复
if(next.indexOf(currentSubstring[j])===-1){
//如果不重复的话，把它拼接给next字符串，然后继续内层循环
next+=currentSubstring[j];
continue;
}else{
//若某次循环发现了在next中已经出现了该字符
//那么直接把next push进结果数组substrings，然后跳出内层循环
substrings.push(next);
next="";
break;
}
}
//假如我们传入的字符串只有一位，那么内层循环就无法push进数组，所以我们要在外层检查一下
if(next.length!==0){
substrings.push(next);
next="";
}
}最后我们对存储所有结果的substrings数组遍历查找length最大的成员：
substrings.forEach(function (item) {
if(item.length>=max)max=item.length;
});
return max;我们也可以直接输出substrings看看结果是怎么样的：
func("pwwkew")
[ ''pw'', ''w'', ''wke'', ''kew'', ''ew'', ''w'' ]
func("")
0
func("a")
[ ''a'' ]然后就大功告成啦！下面贴上完整代码：
/**
* @param {string} s
* @return {number}
*/
var lengthOfLongestSubstring = function (s) {
var substrings = [];
var next = "";
var currentSubstring = "";
var max = 0;
if (s.length) {
for (var i = 0; i < s.length; i++) {
currentSubstring = s.substr(i);
for (var j = 0; j < s.length - i; j++) {
if (next.indexOf(currentSubstring[j]) === -1) {
next += currentSubstring[j];
continue;
} else {
substrings.push(next);
next = "";
break;
}
}
if (next.length !== 0) {
substrings.push(next);
next = "";
}
}
substrings.forEach(function (item) {
if (item.length >= max) max = item.length;
});
return max;
} else {
return 0;
}
};
关于395. Longest Substring with At Least K Repeating Characters的介绍现已完结，谢谢您的耐心阅读，如果想了解更多关于003_LongestSubstringWithoutRepeatingCharacters、3. Longest Substring Without Repeating Characters、3_Longest Substring Without Repeating Characters -- LeetCode、JS算法——Longest Substring Without Repeating Characters的相关知识，请在本站寻找。
本文标签：
![[转帖]Ubuntu 安装 Wine方法（ubuntu如何安装wine）](https://www.gvkun.com/zb_users/cache/thumbs/4c83df0e2303284d68480d1b1378581d-180-120-1.jpg)
