Length of Longest Substring Without Repeating Characters
Problem (from Leetcode)
Given a string, find the length of the longest substring without repeating characters.
Examples
Given abcabcbb
, the answer is abc
, which the length is 3
.
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 a substring, pwke
is a subsequence and not a substring.
Discussion
Approach
- Keep track of the substring characters in a
Set
. - Keep track of the evaluated ("seen") characters in a
Queue
. - Iterate through the characters in the input
String
.- If the substring characters include the current character
- Iterate through the head of the seen characters
Queue
until you find a match in theQueue
. - For each non-matching character from the
Queue
, remove it from theQueue
and remove it from theSet
. - Once you find a matching character, remove it from the head of the
Queue
and add it to the tail of theQueue
.
- Iterate through the head of the seen characters
- Else
- Add the current character to the
Set
- Add the current character to the tail of the
Queue
.
- Add the current character to the
- If the
size
of theSet
is greater than the current longest substring length, replace the current longest substring length with theSet
size
.
- If the substring characters include the current character
General Questions
- Naming sucks - open to a better name - there's gotta be something better than
LongestSubstringWithoutRepeatingCharactersLengthIdentifier
...right? - Is there a cleaner implementation that uses other data structures?
Implementation
import java.util.HashSet;
import java.util.Queue;
import java.util.Set;
import java.util.concurrent.LinkedBlockingQueue;
public class LongestSubstringWithoutRepeatingCharactersLengthIdentifier {
public static int identify(String s) {
int longestSubstringLength = 0;
Set<Character> substringCharacters = new HashSet<>();
Queue<Character> seenCharacters = new LinkedBlockingQueue<>();
for (char currentCharacter : s.toCharArray()) {
if (substringCharacters.contains(currentCharacter)) {
while (seenCharacters.peek() != currentCharacter) {
substringCharacters.remove(seenCharacters.poll());
}
seenCharacters.poll();
} else {
substringCharacters.add(currentCharacter);
}
seenCharacters.add(currentCharacter);
if (substringCharacters.size() > longestSubstringLength) {
longestSubstringLength = substringCharacters.size();
}
}
return longestSubstringLength;
}
}
max...
instead oflongest...
? \$\endgroup\$