Given a string s, find the length of the longest substring without repeating characters.
Input: s = "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.
Input: s = "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.
Input: s = "pwwkew"
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
- s consists of English letters, digits, symbols and spaces.
Contents
- 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 left and right,
take the length of longest substring length found so far, and when a character is repeated, move the left pointer to where the duplicate was found.
Implementation steps:
-
First, we will create four variables left, right that we will use to adjust the window, longest to hold the result, and a
HashSet dups to track the duplicate characters.
-
Next, run a while loop until right pointer reaches end of array, and check:
-
If the current character found in dups: This means that a duplicate character was found, so adjust left pointer
to its next position where the duplicate was found, also remove all other characters until that position from dups.
For example consider the input string "abcdEfghEijdklmno, when we reach 2nd character 'E', a duplicate already exists,
so we will move our left pointer to next position of 1st 'E' character, i.e. to character 'f' position, and also remove all characters from dups 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.
-
Next, check longest window substring found so far using Math.max(longest, right - left +1) (+1 because indexes are off by 1).
-
Then, add current character to the dups and increment right pointer.
-
Finally, return the longest.
In the above implementation, we have used HashSet to find the duplicates, we can replace that with an array as well, if we know that the character set are ASCII characters.
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 n is the length of input string s.
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
GitHub link for Java code