使用双指针实现滑动窗口。
1、初始化滑动窗口ls_ch=set();
2、初始化变量left=0,代表滑动窗口最左边元素的索引;
3、初始化变量res=0,代表最大无重复字符的子串长度;
4、遍历字符串s;当s[right]出现在滑动窗口ls_ch中时,从滑动窗口的最左边依次删除元素直到s[right]并删除同时更新该窗口最左边元素的索引;将s[right]加入ls_ch。更新res的值为max(res,right-left+1)。
5、返回res。
核心:找到最近的与s[j]相等的元素的索引i且当前i必须大于上一轮的i,j-i为该子串的长度。返回这些子串的最大长度。
举例如下:
例1:abcabcbb
【a】bcabcbb:right=0,s[right]="a",滑动窗口为【a】,left=0,res=max(0,0-0+1)=1
【ab】cabcbb:right=1,s[right]="b",滑动窗口为【ab】,left=0,res=max(1,1-0+1)=2
【abc】abcbb:right=2,s[right]="c",滑动窗口为【abc】,left=0,res=max(2,2-0+1)=3
a【bca】bcbb:right=3,s[right]="a",滑动窗口为【bc】+a,left=1,res=max(3,3-1+1)=3
ab【cab】cbb:right=4,s[right]="b",滑动窗口为【ca】+b,left=2,res=max(3,4-2+1)=3
abc【abc】bb:right=5,s[right]="c",滑动窗口为【ab】+c,left=3,res=max(3,5-3+1)=3
abcab【cb】b:right=6,s[right]="b",滑动窗口为【c】+b,left=5,res=max(3,6-5+1)=3
abcabcb【b】:right=7,s[right]="b",滑动窗口为【】+b,left=7,res=max(3,7-7+1)=3
例2:abba
【a】bba:right=0,s[right]="a",滑动窗口为【a】,left=0,res=max(0,0-0+1)=1
【ab】ba:right=1,s[right]="b",滑动窗口为【ab】,left=0,res=max(1,2-0+1)=2
ab【b】a:right=2,s[right]="b",滑动窗口为【】+b,left=2,res=max(2,2-2+1)=2
ab【ba】:right=3,s[right]="a",滑动窗口为【b】+a,left=2,res=max(2,3-2+1)=2