Longest Substring with At Most Two Distinct
2024-08-25 00:21:09
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.
用p1 & p2 两个pointer分别纪录当前window里两个character最后一次发生时的index,用start纪录window开始时的index。
从index 0开始遍历String:
如果当前的character在window内,update相应的pointer。
如果不在,比较两个character的pointer,去掉出现较早的那个character, 更新start=min(p1,p2)+1
时间复杂度是O(n), 空间复杂度是O(1):
public class Solution {
public int lengthOfLongestSubstringTwoDistinct(String s) {
int result = 0;
int first = -1, second = -1;
int win_start = 0;
for(int i = 0; i < s.length(); i ++){
if(first < 0 || s.charAt(first) == s.charAt(i)) first = i;
else if(second < 0 || s.charAt(second) == s.charAt(i)) second = i;
else{
int min = first < second ? first : second;
win_start = min + 1;
if(first == min) first = i;
else second = i;
}
result = Math.max(result, i - win_start + 1);
}
return result;
}
}
最新文章
- android EditText inputType说明
- iOS - (集成支付宝SDK大坑总结)
- 怎么学习C++?
- 使用VAssistX给文件和函数添加注释-2015.12.31
- codevs 1922 骑士共存问题 网络流
- 解决MyEclipse吃内存以及卡死的方法 (转)
- Hibernate table schema 的设置与应用
- html5 geolocation配合百度地图api实现定位
- 剑指Offer——中国银行面试知识储备
- No X11 DISPLAY variable was set
- MVC object htmlAttributes,IDictionary<;string, object>; htmlAttributes 写法
- better-scroll项目中遇到的问题
- 2018牛客网暑假ACM多校训练赛(第三场)D Encrypted String Matching 多项式 FFT
- 2018年高教社杯全国大学生数学建模竞赛A题解题思路
- Nop 4.1版本已经迁移到.net core2.1版本
- 『转』VC++ webbrowser函数使用范例
- BZOJ1398: Vijos1382寻找主人 Necklace 字符串最小表示法
- Java多线程-Java多线程概述
- crc16算法,包括单片机和c#版本
- Git和Repo管理使用简要介绍
热门文章
- P4427 [BJOI2018]求和
- C# string 的一点属性、方法什么的
- XAF-DevExpress.ExpressApp.DC.Xpo.XpoTypeInfoSource 生成实体的过程-学习笔记
- zabbix3.4 监控路由器报错No Such Instance currently exists at this OID
- Idea for Mac 快捷键(快捷键选择:Mac OS X 10.5+)
- shell小记
- vue mock(模拟后台数据) 最简单实例(一)——适合小白
- pytorch中的Linear Layer(线性层)
- MySQL基础练习(二)
- python循环综合运用