文件名称:
README.md
所在目录:
教材与参考资料 / 程序设计类 / 数据结构＆算法 / 算法 / 面试与力扣题目详解 / Leetcode题目和解答 / java-leetcode / longest-substring-with-at-most-two-distinct-characters
文件大小:
763.00 B
下载地址:
文本预览:
## Relative of [Minimum Window Substring](../minimum-window-substring)
This problem is a litte easier than [Minimum Window Substring](../minimum-window-substring).
## Loop invariant
Assume that `S` is a `string with at most two distinct char`
when a new char `c` comes:
* append it to `S`'s right
* trim from `S`'s left, remove one char until `S` is a `string with at most two distinct char`
```
S = 'aabb'
new char c = 'c'
S = 'aabbc'
S is not `string with at most two distinct char`
so remove a from S
S = 'abbc'
S is not `string with at most two distinct char`
so remove a from S
S = 'bbc'
```
## Finding max
after each loop, `S` is a `string with at most two distinct char`. but, its length changes.
what we need is to find the max length.
This problem is a litte easier than [Minimum Window Substring](../minimum-window-substring).
## Loop invariant
Assume that `S` is a `string with at most two distinct char`
when a new char `c` comes:
* append it to `S`'s right
* trim from `S`'s left, remove one char until `S` is a `string with at most two distinct char`
```
S = 'aabb'
new char c = 'c'
S = 'aabbc'
S is not `string with at most two distinct char`
so remove a from S
S = 'abbc'
S is not `string with at most two distinct char`
so remove a from S
S = 'bbc'
```
## Finding max
after each loop, `S` is a `string with at most two distinct char`. but, its length changes.
what we need is to find the max length.
点赞
回复
X