Longest Substring Without Repeating Characters
Given a string, find the length of thelongest substringwithout repeating characters.
Examples:
Given"abcabcbb"
, the answer is"abc"
, which the length is 3.
Given"bbbbb"
, the answer is"b"
, with the length of 1.
Given"pwwkew"
, the answer is"wke"
, with the length of 3. Note that the answer must be asubstring,"pwke"
is asubsequenceand not a substring.
Here is a solution.
class Solution {
public int lengthOfLongestSubstring(String s) {
// iterate through letters and put all chars into set, until it is found in the set
// if found in the set, return cursor to previous start + 1 (i-size) and continue reading from there
int max = 0;
int count = 0;
Set<Character> set = new HashSet<>();
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (set.contains(c)) {
int size = set.size();
set.clear();
count = 0;
i = i - size;
} else {
set.add(c);
count++;
max = Math.max(max, count);
}
}
return max;
}
}
Last updated
Was this helpful?