# O(n) Java solution using Set

• Assuming a perfect hash function this is O(n) solution. The Set is actually used like a sliding window.

Simple logic is

1. Have two pointers start and end. Initially start = 0 and end =1;
2. Add end to set. Increment end and check if set size == end-start.
3. If yes and update max variable.
4. If not then increment start will set size = end-start

Be careful of certain corner cases like "aab", "a" "aa" etc.

``````public static int lengthOfLongestSubstring(String s) {

if(s.length()<=1) { return s.length();}
Set<Character> set = new HashSet<>();

int start = 0;
int end = 1;
int max = 1;
while(end < s.length()){
//System.out.println("Set is "+set);
max = Math.max(set.size(),max);
end++;
//System.out.println("Set Size = "+set.size()+"\t"+(end-start));
while(set.size()<(end-start)){
if(s.charAt(start)!=s.charAt(end-1)){
set.remove(s.charAt(start));
}
start++;
//System.out.println("Moving start : Set Size = "+set.size()+"\t"+(end-start)+"\t"+set);
}
// System.out.println("Start is "+start);
//  System.out.println("End is "+end);
}

return max;

}``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.