Sliding window to solve "longest substring, no repeating chars" Question: Longest Substring Without Repeating Characters


  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.
  
  Given "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.


Solution:
We use a sliding window to define the current substring. In my solution, we start with head = position 0 and tail = position 0 in a way where
[H][T]a b c a b c b b and NO characters have been marked as "seen". After the first iteration, head=0, tail=1, our positioning is [H]a[T]b c a b c b b and our first character a at position 0 has been seen.

We then advance the tail and add the character seen to a hashmap hm. If we've already seen this character, we advance the head point to one position past the position the character was last seen. We are done once the tail position is equal to the length of the string.



Why I am posting here asking for feedback is that my #1 concern is that there's no proper way to define my sliding window method. How am I supposed to explain my method to an interviewer? I can't define it mathematically, as it's not [head, tail) nor is it (head, tail). What would be a way to improve my sliding window method so that it's well-defined and I can re-use this strategy every time I need to use a sliding window ?

class Solution {
    int head = 0;
    int tail = 0;
    int max = 0; // current max length

    public int lengthOfLongestSubstring(String s) {
        Map&lt;Character, Integer&gt; hm = new HashMap&lt;&gt;(); // value = position of character
        int currSize = 0;

        while(tail &lt; s.length()) {
            tail++;
            char curr = s.charAt(tail-1);
            if (!(hm.containsKey(curr) &amp;&amp; hm.get(curr) &gt;= head)) {
                hm.put(curr, tail-1);
                compareMax(++currSize);
            } else {
                head = hm.get(curr)+1;
                hm.put(curr, tail-1);
                currSize = tail-head;
            }
            System.out.println("head: " + head + ", tail: " + tail + ", size: " + currSize);
        }
        return max;
    }

    void compareMax(int currSize) {
        if (currSize &gt; max) {
            max = currSize;
        }
    }
}


Output for 'abcabcbb':

head: 0, tail: 1, size: 1
head: 0, tail: 2, size: 2
head: 0, tail: 3, size: 3
head: 1, tail: 4, size: 3
head: 2, tail: 5, size: 3
head: 3, tail: 6, size: 3
head: 5, tail: 7, size: 2
head: 7, tail: 8, size: 1
Summary: stay with your implementation.

I don't think a re-usable sliding window fits well to your algorithm.

What are the operations that come to one's mind with both a generic sliding String window and with your algorithm (I'll stay with your terminology of head and tail, although personally I'd name them just the other way round)?


advanceHead() generic op, not used by your algo (see jumpHead())
advanceTail() generic op, used by your algo
jumpHead(int newPos) only specific to your algo
getSubstring() generic op, not used by your algo
findInSubstring(char ch) maybe generic op, not really used by your algo (see below method)
lastOccurrenceBeforeTail(char ch) used by your algo, but I wouldn't expect such a method in a generic sliding window


So, there's hardly any overlap between your algo's sliding window and operations one would expect from a re-usable generic sliding window.

If you'd extract a sliding window from your algorithm, it would be burdened by quite specific methods that no-one else would ever use.

If you were to use a generic sliding window in your algorithm, you'd still have to maintain the character-positions storage and do the head-jumping individually.

One optional refactoring of your code could be to extract a NonRepeatingSlidingWindow with two public methods:


advance() increments the tail, jumps the head if necessary and returns a "finished"-flag
getLength() returns the current size of the sliding window.