找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 1695|回复: 1
收起左侧

[米群网刷题小分队] 【LeetCode小分队】【Longest Substringwith At Most Two Distinct Characters】

[复制链接]

90

主题

46

精华

1908

积分

版主

Rank: 7Rank: 7Rank: 7

积分
1908

热心会员突出贡献优秀版主最佳新人精华帖之王活跃会员

发表于 12-6-2014 10:21 PM | 显示全部楼层 |阅读模式

亲!马上注册或者登录会查看更多内容!

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
快速通道:
https://oj.leetcode.com/problems/longest-substring-with-at-most-two-distinct-characters/

题目:
Given a string, find the length of the longest substring T that contains at most 2 distinct characters.
For example, Given s = “eceba”,
T is "ece" which its length is 3.

建议的回复格式:(如果大家有更好的格式可以补充哦)
思路:(必填)
代码:(必填)
复杂度分析:(必填)
细节和陷阱:(选填)
相似题目:(选填)


=========点击传送门查看所有题目哟========
                            汇总贴 传送门
==================================

90

主题

46

精华

1908

积分

版主

Rank: 7Rank: 7Rank: 7

积分
1908

热心会员突出贡献优秀版主最佳新人精华帖之王活跃会员

 楼主| 发表于 12-6-2014 11:48 PM | 显示全部楼层
本帖最后由 cpcs 于 12-7-2014 02:18 AM 编辑

[cpcs 题解]
原帖地址: http://www.meetqun.com/forum.php ... tid=2846&fromuid=12


思路:
维护一个窗口 [i..j],保证[i..j]里面最多有两种字符。
(1) 如果当前窗口字符种类不超过两个,我们可以向右滑动j,直到出现第三种字符,同时统计一下两种字符出现的次数。
(2) 当j滑动到指向第三种字符,我们向右滑动i,同时减少对应字符的个数,在滑动到j之前,必然出现 [i..j - 1]只有一种字符的情况,这时[i..j]就有两种字符了。
于是重复(1)和(2)就可以了。
陷阱:注意下标越界的特殊情况。 还有出现字符的种类,只有一种字符的时候,我们认为它是c1……
拓展:用类似的方法可以拓展到窗口里最多只有k种字符的情况,当然需要一个hash表,或者直接用数组下标[0..255]统计每种字符个数。
本质:动态维护窗口里字符种类和个数,左边界滑动,移出字符,对应减1。右边界滑动,移入字符,对应加1。

相似题目:
Minimum Window Substring



回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

快速回复 返回顶部 返回列表