问题
给定一个字符串，找到最多有k个不同字符的最长子字符串，并返回其长度。
样例
例如，给定 s = "eceba" , k = 3,
T 是 "eceb"，长度为 4.
第一种思路
将母问题分为两个子问题：
1.如果从从头开始找，求最长k不同子串长度
2.如果从第二个字符开始找，求最长k不同子串长度
然后不断循环递归
实现
public static int longestSubstringDistinct(String s, int k) {
// write your code here
//边界，当查找就剩最后k个字符或更少的时候，最长子串长度为当前长度
if (s.length() <= k) return s.length();
//分成两个子问题
//第一个子问题：如果从当前字符串从头开始找，求最长k不同子串长度
//创建一个HashSet，仅存储k个不同的字符
HashSet<Character> kDinstinct = new HashSet<>();
int p = 0;
while (p < s.length()) {
//在HashSet中存储k个字符，超过的抛弃掉
if (kDinstinct.size() < k) {
kDinstinct.add(s.charAt(p));
}
//检查k个不同字符中是否包含当前字符
if (kDinstinct.contains(s.charAt(p))) {
p++;
} else {
break;
}
}
System.out.println(p);
//第二个子问题：如果从当前下一个index找，求最长k不同子串长度
int subLength = longestSubstringDistinct(s.substring(1, s.length()), k);
//开始收集子问题的结果
return Math.max(subLength,p);
}
这种实现方式看似没有什么大问题，但是，当数据量很大的时候，频繁的在JVM中创建递归方法的栈帧，很快的就会发生StackOverFlow异常！所以，来看下第二种思路的改进！
第二种思路
基于第一种思路，不过改为尝试用循环来替代递归，避免发生虚拟机栈溢出。
实现
public static int lengthOfLongestSubstringKDistinct(String s, int k) {
// write your code here
//边界，当查找就剩最后k个字符或更少的时候，最长子串长度为当前长度
if (s.length() <= k) return s.length();
int result = 0;
for (int i = 0; i < s.length() - k; i++) {
int p = 0;
String subS = s.substring(i, s.length());
//创建一个HashSet，仅存储k个不同的字符
HashSet<Character> kDinstinct = new HashSet<>();
while (p < subS.length()) {
//在HashSet中存储k个字符，超过的抛弃掉
if (kDinstinct.size() < k) {
kDinstinct.add(subS.charAt(p));
}
//检查k个不同字符中是否包含当前字符
if (kDinstinct.contains(subS.charAt(p))) {
p++;
} else {
break;
}
}
result = Math.max(result, p);
}
return result;
}
第二种思路基本符合要求了，但是时间复杂度仍然为平方阶，接下来改进时间复杂度，提供给大家一个线性阶的思路。
第三种思路
采用双指针，用HashMap记录双指针中间的字符串是否满足要求
实现
public static int lengthOfLongestSubstringKDistinct(String s, int k) {
// write your code here
int result = 0;
int left = 0;
//声明一个HashMap，用来存储k Distinct，还可以根据value用来判断元素是否可以删除
HashMap<Character, Integer> map = new HashMap<>();
for (int right = 0; right < s.length(); right++) {
//右指针依次把字符串中的字符放到map中
map.put(s.charAt(right),right);
//当map元素大于k Distinct时，得到满足要求的子字符串
while (map.size() > k) {
// 删除最左的字符，删除成功，则退出循环
char leftChar = s.charAt(left);
if (map.get(leftChar) == left) {
map.remove(leftChar);
}
// 左指针右移
left++;
}
//子结果即左右指针之间的长度
int subResult = right - left + 1;
//结果取最大
result = Math.max(result,subResult);
}
return result;
}
如果文章对你有帮助的话，不要忘记打赏小编哟~
