Given a string with repeated and no repeated characters, we want to find the longest substring without repeating.
Example 1:
abcabcd
Ans = 4 since abcd is the longest substring with no repeated character in the substring. All chars are unique.
Example 2:
lemenmetahm
Ans: 5 since metah is the longest substring with no repeated character in the substring.
Example 3: abcdeabceghedt
Ans: 6 since abcegh is the longest substring with no repeated character in the substring.
Explanation:
Here we want to use a Hashset data structure to solve this problem in linear time.
We need two variable to track the position of the chars in the string. One will be the starting point and the other one will be the end point of the non repeating substring.
Let us say i tracks the starting where as j tracks the ending
We also want to save each char to hashset as we traverse the string using j.
we also want to calculate the length of non-repeating char as we traverse and update it if we find a new substring longer than the previous value.
public int LengthOfLongestSubstring(String s) {
int n = s.Length;
HashSet<char> set = new HashSet<char>();
int ans = 0, i = 0, j = 0;
while (i < n && j < n) {
if (!set.Contains(s[j])) {
set.Add(s[j]);
j++;
ans = Math.Max(ans, j - i);
}
else {
set.Remove(s[i]);
i++;
}
}
return ans;
}