字符串-至多包含K种字符的子串中最长子串(mid)

一、题目描述

二、解题思路

借鉴以下题目思想，使用双指针，外层循环右侧指针移动，内存循环左侧指针移动

字符串-最长不含重复字符的子字符串(mid)-CSDN博客文章浏览阅读622次，点赞17次，收藏4次。java刷题：求最长不含重复字符的子字符串，使用双指针结合题目要求，减少左指针的移动次数，降低程序执行复杂度，这个题目很好，值得好好理解。https://blog.csdn.net/hehe_soft_engineer/article/details/139320167题目要求K种字符，则设置一个规模大小为K的hashset，该hashset记录当前至多包含K种字符的子串所含的字符类型。

1.当hashset所含字符种类小于K时，右指针++。

2.当hashset所含字符种类等于K时：

        2.1当右指针指向的字符在hashset中，右指针++

        2.2当右指针指向字符不在hashset中，找到当前子字符串中最久未出现的字符，定位到字符位置，将左指针指向该字符后一个位置，右指针++，以实现更新至多包含K种字符的子串。

 3.如果当前子串长度变长了，则更新记录最长长度的变量。

三、代码实现

import java.util.*;public class Solution {/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可** * @param s string字符串 * @param k int整型 * @return int整型*/public int longestSubstring (String s, int k) {// 设置left和right双指针int left=0,right=0;HashSet<Character> charset=new HashSet<>();charset.add(s.charAt(0));int maxLen=0;for(;right<s.length();right++){if(charset.contains(s.charAt(right))){//此时不做操作}else{if(charset.size()<k){//当前字符种类并没有达到k，添加字符种类charset.add(s.charAt(right));}else{//此时需要从右侧开始找到第k次读取的字符(替换出set)int icounter=0;int leftdeletIndex=right-1;HashSet<Character> tmpcharset=new HashSet<>();while(leftdeletIndex>=left){if(!tmpcharset.contains(s.charAt(leftdeletIndex))){tmpcharset.add(s.charAt(leftdeletIndex));}if(tmpcharset.size()==k){//此时leftdeletIndex就是需要移除的字符tmpcharset.clear();break;}leftdeletIndex--;}left=leftdeletIndex+1;charset.remove(s.charAt(leftdeletIndex));charset.add(s.charAt(right));}}maxLen=maxLen>(right-left+1)?maxLen:(right-left+1);}return maxLen;}
}

四、刷题链接

至多包含K种字符的子串_牛客题霸_牛客网