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
