Longest Substring Without Repeating Characters
Given a string s
Example 1
Output: 3
Explanation: The answer is "abc", with the length of 3.
Example 2
Output: 1
Explanation: The answer is "b", with the length of 1.
Example 3
Output: 3
Explanation: The answer is "wke", with the length of 3.
Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.
Constraints:
0 <= s.length <= 5 * 104 consists of English letters, digits, symbols and spaces.s
Solution 1 - Using sliding window technique, and HashSet to find duplicates
In this approach, we are going to apply sliding window technique, using two pointers leftrightleft
Implementation steps:
-
First, we will create four variables
,left that we will use to adjust the window,right to hold the result, and alongestHashSet to track the duplicate characters.dups -
Next, run a
loop untilwhile pointer reaches end of array, and check:right-
If the current character found in
: This means that a duplicate character was found, so adjustdups pointer to its next position where the duplicate was found, also remove all other characters until that position fromleft .dups
For example consider the input string , when we reach 2nd character 'E', a duplicate already exists, so we will move our"abcdEfghEijdklmno pointer to next position of 1st 'E' character, i.e. to character 'f' position, and also remove all characters fromleft until that position, otherwise it will find another duplicate for letter 'd', but the first letter 'd' at position 4, is previous to the first duplicate of 'E', in other words we are moving our window size to a position where the duplicate was found.dups -
Next, check longest window substring found so far using
(+1 because indexes are off by 1).Math.max(longest, right - left +1) -
Then, add current character to the
and incrementdups pointer.right
-
If the current character found in
-
Finally, return the
.longest
Note:
In the above implementation, we have used HashSet
import java.util.HashSet;
public class LongestSubstringWithoutRepeatingCharacters {
static int lengthOfLongestSubstring(String s) {
// Note that HashSet can be replaced with array[128] if the characters are ascii (see below method)
HashSet<Character> dups = new HashSet<>();
int left = 0;
int right = 0;
int longest = 0;
while(right < s.length()) {
char current = s.charAt(right);
while (dups.contains(current)) {
// move left index to where the duplicate was found
// and remove all characters until that left index
dups.remove(s.charAt(left++));
}
longest = Math.max(longest, right-left+1);
dups.add(current);
right++;
}
return longest;
}
static int lengthOfLongestSubstring_Using_Array_ASCII(String s) {
// This is same as above, we are replacing HashSet with int[] array, assuming characters are ascii
int[] dups = new int[128];
int left = 0;
int right = 0;
int longest = 0;
while(right < s.length()) {
char current = s.charAt(right);
while(dups[current] != 0) {
dups[s.charAt(left)] -= 1;
left++;
}
longest = Math.max(longest, right - left +1);
dups[current] += 1;
right++;
}
return longest;
}
public static void main(String[] args) {
System.out.println("########### Sliding Window, and find duplicates using a HashMap #############");
System.out.println(lengthOfLongestSubstring("abcabcbb"));
System.out.println(lengthOfLongestSubstring("bbbbb"));
System.out.println(lengthOfLongestSubstring("pwwkew"));
System.out.println(lengthOfLongestSubstring(" "));
System.out.println("########### Sliding Window, and find duplicates using an array (ascii) #############");
System.out.println(lengthOfLongestSubstring_Using_Array_ASCII("abcabcbb"));
System.out.println(lengthOfLongestSubstring_Using_Array_ASCII("bbbbb"));
System.out.println(lengthOfLongestSubstring_Using_Array_ASCII("pwwkew"));
System.out.println(lengthOfLongestSubstring_Using_Array_ASCII(" "));
}
}
Complexity Analysis:
Time complexity: Above code runs in O(n) time where ns
Space complexity: O(n) if the character set is unknown, O(1) if the character set is ASCII.
Above implementations source code can be found at