题意:给定一个字符串,求所有不包含重复字符的子串中最长的是多少。
算法:双指针算法。
1.令指针$i,j$指向串的元素。初始指向$0$的位置。
2.接下来,$i$不断向右移动,直到串$s[j:i+1]$不是合法的子串。
3.j向右移动$1$个单位。
4.重复2,3直到i超出字符串长度限制。
时间复杂度:$O(n)$
public class Solution
{
public int LengthOfLongestSubstring(string s)
{
int ans=0;
HashSet<char> hs=new HashSet<char>();
for(int i=0,j=0;i<s.Length;)
{
while(i<s.Length && !hs.Contains(s[i]))
{
hs.Add(s[i]);
i++;
}
ans=Math.Max(ans,hs.Count);
if(i>=s.Length)
{
break;
}
hs.Remove(s[j]);
j++;
}
return ans;
}
}