题目描述
给定一个字符串 s ，找出 至多 包含两个不同字符的最长子串 t ，并返回该子串的长度。
示例 1:
输入: "eceba"
输出: 3
解释:
t 是 "ece"，长度为3
示例 2:
输入: "ccaabbb"
输出: 5
解释:
t 是 "aabbb"，长度为5。
数据结构
- 指针、哈希表
算法思维
- 遍历、双指针、哈希（散列）
解题要点
- “范围问题” 或 “同步变化” ==> 双指针
- “快速查找” 或 “重复匹配” ==> 哈希表
解题思路
一. Comprehend 理解题意
- 要求是子串，不是子序列
- 子串最多由两个不同字符 按任意数量 排列组合而成
- 不要求记录子串，只需要记录长度
二. Choose 选择数据结构与算法
双指针 + 哈希表 解法
- 数据结构：指针、哈希表
- 算法思维：遍历、双指针、哈希（散列）
解题思路
- 声明一个哈希表和一个哈希函数
哈希函数用于生成字符索引
哈希表存放该字符在子串中出现的个数 - 声明一个整形变量存放“不同字符”的个数，按照题目要求，此个数应当 <= 2
- 用左右两个指针遍历整个字符串
判断右指针字符是否是“新字符”
如果是新字符，不同字符数 +1
无论是否为新字符，右指针在哈希表中相应位置的数据都要 +1，表示右指针字符在子串中出现的次数 +1
不断判断不同字符数是否 > 2
如果大于2，左指针在哈希表中相应位置的数据 -1，表示左指针字符在子串中出现的次数 -1
判断左指针在哈希表中相应位置的数据是否 == 0
如果不为 0，说明当前删除的左指针字符不是子串中的“最后一个”，右移左指针
如果为 0，说明当前删除的左指针字符是子串中的“最后一个”，不同字符数 -1 - 不管任何情况，右指针都照常右移
- 每次右指针右移时，计算最长子串的长度
边界问题
- 右指针（b）领先左指针（a），因此边界条件为：
b < s.length()
细节问题
- 子串长度的计算公式：
如果先计算长度，右指针再右移，则subLen = b - a +1
如果右指针先右移，再计算长度，则subLen = b - a
三. Code 编码实现基本解法
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;
}
}
执行耗时：1 ms，击败了 100.00% 的Java用户
内存消耗：36.6 MB，击败了 99.63% 的Java用户
时间复杂度：O(n) -- 两次链表的遍历 O(n)，查询哈希表 O(1)
空间复杂度：O(1) -- 一个哈希表 O(1)，两个指针 O(1)，两个整数变量 O(1)
四. Consider 思考更优解
改变算法思维
- 使用“滑动窗口”的算法思维解决问题
五. Code 编码实现最优解
优化解法
/**
* 解法一：采用滑动窗口的算法思想，选取 left-right 子串进行验证
* 如果字符数量没有超过2，则记录此时的最大长度，并且 right++
* 如果字符数量超过2，则 left++
* 使用 map 存放出现过的字符及次数
*
* （优化算法，使用数组替代 map)
*/
public int lengthOfLongestSubstringTwoDistinct1(String s) {
char[] chars = s.toCharArray();
int len = chars.length;
Map<Character, Integer> map = 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;
}
执行耗时：4 ms，击败了 85.81% 的Java用户
内存消耗：36.8 MB，击败了 96.08% 的Java用户
时间复杂度：O(n) -- 字符串的遍历 O(n)，哈希表的查询 O(1)
空间复杂度：O(1) -- 定长的哈希表 O(1)，双指针 O(1)
六. Change 变形与延伸
=== 待续 ===
网友评论