LeetCode刷题实战159:至多包含两个不同字符的最长子串
Given a string, find the length of the longest substring T that contains at most 2 distinct characters.
题意
例 1:
输入: “eceba”
输出: 3
解释: t 是 “ece”,长度为3。
例 2:
输入: “ccaabbb”
输出: 5
解释: t 是 “aabbb”,长度为5。
解题
解题思路
一. 理解题意
要求是子串,不是子序列
子串最多由两个不同字符 按任意数量 排列组合而成
不要求记录子串,只需要记录长度
二. 选择数据结构与算法
双指针 + 哈希表 解法
数据结构:指针、哈希表
算法思维:遍历、双指针、哈希(散列)
解题思路
声明一个哈希表和一个哈希函数
哈希函数用于生成字符索引
哈希表存放该字符在子串中出现的个数声明一个整形变量存放“不同字符”的个数,按照题目要求,此个数应当 <= 2
用左右两个指针遍历整个字符串
判断右指针字符是否是“新字符”
如果是新字符,不同字符数 +1
无论是否为新字符,右指针在哈希表中相应位置的数据都要 +1,表示右指针字符在子串中出现的次数 +1
不断判断不同字符数是否 > 2
如果大于2,左指针在哈希表中相应位置的数据 -1,表示左指针字符在子串中出现的次数 -1
判断左指针在哈希表中相应位置的数据是否 == 0
如果不为 0,说明当前删除的左指针字符不是子串中的“最后一个”,右移左指针
如果为 0,说明当前删除的左指针字符是子串中的“最后一个”,不同字符数 -1不管任何情况,右指针都照常右移
每次右指针右移时,计算最长子串的长度
边界问题
右指针(b)领先左指针(a),因此边界条件为:
b < s.length()
细节问题
子串长度的计算公式:
如果先计算长度,右指针再右移,则subLen = b - a +1
如果右指针先右移,再计算长度,则subLen = b - a
class Solution {
public int lengthOfLongestSubstringTwoDistinct(String s) {
int len = s.length();
//定义哈希表
int[] hashtable = new int[128];
for (int i = 0; i < 128; i++){
hashtable[i] = 0;
}
int a = 0; //左指针
int b = 0; //右指针
int count = 0; //不同字符的个数
int subLen = 0; //最长子串的长度
//遍历字符串
while (b < len) {
char cb = s.charAt(b);
//如果 b 处字符不存在于哈希表中
if (hashtable[hash(cb)] == 0){
count++; //不同字符个数 +1
}
//哈希表对应位置 +1
hashtable[hash(cb)]++;
//直到不同字符个数 <= 2
while (count > 2){
char ca = s.charAt(a);
hashtable[hash(ca)]--; //哈希表中 a 处字符对应位置 -1
//如果哈希表中 a 处字符对应位置不为 0
if (hashtable[hash(ca)] == 0){
count--; //不同字符个数 -1
}
a++; //a指针右移
}
//计算子字符串长度
subLen = Math.max(subLen,b-a+1);
b++;
}
return subLen;
}
//定义哈希函数
private int hash(char c){
return c;
}
}
内存消耗:36.6 MB,击败了 99.63% 的Java用户
时间复杂度:O(n) -- 两次链表的遍历 O(n),查询哈希表 O(1)
空间复杂度:O(1) -- 一个哈希表 O(1),两个指针 O(1),两个整数变量 O(1)
使用“滑动窗口”的算法思维解决问题
优化解法
/**
* 解法一:采用滑动窗口的算法思想,选取 left-right 子串进行验证
* 如果字符数量没有超过2,则记录此时的最大长度,并且 right++
* 如果字符数量超过2,则 left++
* 使用 map 存放出现过的字符及次数
*
* (优化算法,使用数组替代 map)
*/
public int lengthOfLongestSubstringTwoDistinct1(String s) {
char[] chars = s.toCharArray();
int len = chars.length;
Mapmap = new HashMap<>();
int left = 0, right = 0;
int count = 0;//不同的字符数量
int maxLength = 0;
while (right < len) {
//在map中获取该字符出现的次数(不存在则为0),次数+1
int rightNumber = map.getOrDefault(chars[right], 0) + 1;
map.put(chars[right], rightNumber);//更新map
if (rightNumber == 1) {//第一次出现
count++;
}
right++;
if (count <= 2) {
maxLength = Math.max(maxLength, right - left);
}
while (count > 2) {
//左侧移除一个字符,在map中获取该字符出现的次数-1
int leftNumber = map.get(chars[left]) - 1;
map.put(chars[left], leftNumber);//更新map
if (leftNumber == 0) {
count--;
}
left++;
}
}
return maxLength;
}
最优解
/**
* 最优解
* 改进1:考虑 ASCII 码表中的128个字符,可以使用数组代替 map,存放每个字符出现的次数
* 改进2:滑动窗口 只会扩大或者平移(我们要取的就是最大窗口长度)
*
* @param s
* @return
*/
public int lengthOfLongestSubstringTwoDistinct(String s) {
final int length = s.length();
final int[] map = new int[128];
int right = 0, left = 0;
//count 为不同字符的数量
for (int count = 0; right < length; ) {
//右侧新字符进入窗口
if (map[s.charAt(right++)]++ == 0) {
count++;
}
//如果新字符进入窗口后使得 不同字符数量大于2,则左侧窗口也向右滑动一个(窗口平移)
if (count > 2) {
if (--map[s.charAt(left++)] == 0) {
count--;
}
}
}
return right - left;
}
内存消耗:36.8 MB,击败了 96.08% 的Java用户
时间复杂度:O(n) -- 字符串的遍历 O(n),哈希表的查询 O(1)
空间复杂度:O(1) -- 定长的哈希表 O(1),双指针 O(1)