https://app.laicode.io/app/problem/253
Given a string, find the longest substring without any repeating characters and return the length of it. The input string is guaranteed to be not null.
For example, the longest substring without repeating letters for "bcdfbd" is "bcdf", we should return 4 in this case.
Medium
String
The input is not null, nor is it of length 0. In either case, it is considered to have a max length of 0
Use the two pointers/sliding windows approach.
The slow pointer only moves when we see a duplicate character.
The fast pointer only moves when there is no duplicate characters present in the window.
For example,
"a b c d e c f g"
0 1 2 3 4 5 6 7
s →
f →
…
"a b c d e c f g"
0 1 2 3 4 5 6 7
s →
f →
"a b c d e c f g"
0 1 2 3 4 5 6 7
s →
f →
"a b c d e c f g"
0 1 2 3 4 5 6 7
s →
f →
"a b c d e c f g"
0 1 2 3 4 5 6 7
s →
f →
"a b c d e c f g"
0 1 2 3 4 5 6 7
s →
f →
"a b c d e c f g"
0 1 2 3 4 5 6 7
s →
f →
public class Solution {
public int longest(String input) {
// Write your solution here
if (input == null || input.length() == 0) {
return 0;
}
int slow = 0;
int fast = 0;
int maxLen = 0;
Set<Character> seen = new HashSet<>();
while (fast < input.length()) {
if (!seen.contains(input.charAt(fast))) {
// If this character has not appeared before
// 1. add it to the hash set
// 2. move the fast pointer down by one
// 3. update the max length
seen.add(input.charAt(fast));
fast++;
maxLen = Math.max(maxLen, fast - slow);
} else {
// If this character has appeared before
// 1. remove the character that slow points to from the set
// 2. move the slow pointer down by one
seen.remove(input.charAt(slow));
slow++;
}
}
return maxLen;
}
}Time:
There are n characters in the string and there is only one iteration.
So, the time complexity is O(n)
Space:
A HashSet has been created to record the appearance of characters. So, the space complexity is O(n).