【错题集-编程题】包含不超过两种字符的最长字串(滑动窗口)

简介: 【错题集-编程题】包含不超过两种字符的最长字串(滑动窗口)

牛客对应题目链接:包含不超过两种字符的最长子串_牛客题霸_牛客网 (nowcoder.com)


一、分析题目

简单的滑动窗口问题。


二、代码

#include <iostream>
#include <unordered_map>
using namespace std;
 
int main()
{
    string s;
    cin >> s;
    int n=s.size();
    int res=0;
    int cnt=0;
    unordered_map<char, int> hash;
    int left=0, right=0;
    while(right<n)
    {
        hash[s[right]]++;
        if(hash[s[right]]==1) //0->1 多了一种字符
            cnt++;
        while(cnt>2)
        {
            hash[s[left]]--;
            if(hash[s[left]]==0) //1->0 少了一种字符
                cnt--;
            left++;
        }
        res=max(res, right-left+1);
        right++;
    }
    cout << res << endl;
    return 0;
}

三、反思与改进

思路基本没错,还是 “滑动窗口” 系列问题的练习量不够,导致问题考虑的不周到。


相关文章
|
6月前
【每日一题Day159】LC1638统计只差一个字符的子串数目 | 枚举
【每日一题Day159】LC1638统计只差一个字符的子串数目 | 枚举
39 0
|
C语言
【Leetcode-1638.统计只差一个字符的字串数目(C语言)】
【Leetcode-1638.统计只差一个字符的字串数目(C语言)】
43 0
|
5月前
|
算法
【经典LeetCode算法题目专栏分类】【第8期】滑动窗口:最小覆盖子串、字符串排列、找所有字母异位词、 最长无重复子串
【经典LeetCode算法题目专栏分类】【第8期】滑动窗口:最小覆盖子串、字符串排列、找所有字母异位词、 最长无重复子串
|
算法
【算法挨揍日记】day05——209. 长度最小的子数组、3. 无重复字符的最长子串
题目描述: 给定一个含有 n 个正整数的数组和一个正整数 target 。 找出该数组中满足其总和大于等于 target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ,并返回其长度。如果不存在符合条件的子数组,返回 0 。
358 0
|
算法 测试技术
算法强化每日一题--字符串中找出连续最长的数字串
算法强化每日一题--字符串中找出连续最长的数字串
|
存储 数据可视化 算法
字符串之谜:如何找到出现频率最高的字符?
字符串之谜:如何找到出现频率最高的字符?
233 0
|
算法 C++ Python
每日算法系列【LeetCode 424】替换后的最长重复字符
每日算法系列【LeetCode 424】替换后的最长重复字符
每日三题-无重复字符的最长子串、最长连续序列、找到字符串中所有字母异位词
每日三题 无重复字符的最长子串 最长连续序列 找到字符串中所有字母异位词
97 1
每日三题-无重复字符的最长子串、最长连续序列、找到字符串中所有字母异位词
|
索引
力扣刷题记录——748. 最短补全词、744. 寻找比目标字母大的最小字母、747. 至少是其他数字两倍的最大数
力扣刷题记录——748. 最短补全词、744. 寻找比目标字母大的最小字母、747. 至少是其他数字两倍的最大数
134 0
力扣刷题记录——748. 最短补全词、744. 寻找比目标字母大的最小字母、747. 至少是其他数字两倍的最大数
字符串中的单词数(简单难度)
字符串中的单词数(简单难度)
82 0
字符串中的单词数(简单难度)