注册一亩三分地论坛,查看更多干货!
您需要 登录 才可以下载或查看附件。没有帐号?注册账号 
x
最近在刷Google高频题Longest Substring with At Most Two Distinct Characters 的时候发现它和Weekly Contest 123的第四题是同一种类型。
这题的大意是说给出一串数,找到最长的只有两个不同数的子串。变化的形式有:(<= or ==)k unique characters, 统计满足条件的字串个数等。我们只要解决一个最基本的问题:
子串的末尾是j时,找到最小的i使子串(i,j)只有不超过k个不同的数。
这里需要一个unordered_map帮组记录当前的子串出现的数的数量。当字典里的数超过k时移动i,直到字典大小等于K
- 统计at most k unique characters子串数量,每次找到区间(i,j) sum += j-i+1
- 统计正好k unique characters,子串数量,num(at most k) - num(at most k-1)
- 求最长, 每次算出区间直接更新
|