1
\$\begingroup\$

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<Character, Integer> hm = new HashMap<>(); // value = position of character
        int currSize = 0;

        while(tail < s.length()) {
            tail++;
            char curr = s.charAt(tail-1);
            if (!(hm.containsKey(curr) && hm.get(curr) >= 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 > 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
\$\endgroup\$
0
\$\begingroup\$

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.
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.