文章目录
- 题目描述
- 题解思路
- 题解代码
- 题目链接
题目描述
题解思路
本题使用滑动窗口进行求解,使用左指针和右指针分别表示窗口的左边界和窗口的右边界,使用哈希表记录窗口内的字符及其对应数量
我们首先向右移动右指针,将字符加入到哈希表中进行计数,如果当前加入的字符在窗口中超过3个,则右移左指针从窗口中移除元素,直到左指针把当前字符从窗口中移除一个
在移动过程中记录窗口长度的最大值,窗口长度的最大值即为本题结果
题解代码
use std::collections::HashMap;
impl Solution {
pub fn maximum_length_substring(s: String) -> i32 {
let s = s.as_bytes();
let mut map = HashMap::new();
let mut ans = 0;
let mut left = 0;
for i in 0..s.len() {
if let Some(j) = map.get(&(s[i])) {
if *j == 2 {
while s[left] != s[i] {
if let Some(k) = map.get_mut(&s[left]) {
*k -= 1;
}
left += 1;
}
left += 1;
continue;
} else {
map.insert(s[i], j + 1);
}
} else {
map.insert(s[i], 1);
}
ans = ans.max(i - left + 1);
}
ans as i32
}
}
题目链接
https://leetcode.cn/problems/maximum-length-substring-with-two-occurrences/