Identify the Length of the Longest Substring Without Repeating Characters 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 the Queue.
For each non-matching character from the Queue, remove it from the Queue and remove it from the Set.
Once you find a matching character, remove it from the head of the Queue and add it to the tail of the Queue.

Else


Add the current character to the Set
Add the current character to the tail of the Queue.

If the size of the Set is greater than the current longest substring length, replace the current longest substring length with the Set size.



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&lt;Character&gt; substringCharacters = new HashSet&lt;&gt;();
        Queue&lt;Character&gt; seenCharacters = new LinkedBlockingQueue&lt;&gt;();

        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() &gt; longestSubstringLength) {
                longestSubstringLength = substringCharacters.size();
            }
        }
        return longestSubstringLength;
    }
}
LinkedBlockingQueue is not the best choice. It's based on a linked list, which lacks spacial locality. An continuous array-backed queue would be more efficient (there're a few options in the standard library).
 if (substringCharacters.size() &gt; longestSubstringLength) {
     longestSubstringLength = substringCharacters.size();
 }


I'd use the Math.max method here.
You can avoid using the queue altogether. You can keep the leftmost index of the current "window" and the set instead.