Longest Substring without Repeating Characters - Two Pointers / Sliding Window

Problems
1

https://algo.monster/problems/longest_substring_without_repeating_characters

2

some more patterns with Sliding Window: https://leetcode.com/problems/frequency-of-the-most-frequent-element/discuss/1579702/Python-Further-break-down-Sliding-Window-Template

5

In the first example ‘bca’ would also be an acceptable answer along with ‘abc’ and ‘cab’.

6

This is an incomplete definition of a sliding window: “A sliding window is defined by two pointers.”

8

Simpler solution using dictionary to keep track of the last seen repeated character, no set needed.

def longest_substring_without_repeating_characters(s: str) → int:
l = res = 0
seen = {}
for r, ch in enumerate(s):
if ch in seen:
l = max(l, seen[ch] + 1)
res = max(res, r - l + 1)
seen[ch] = r
return res

11

For the longest check in each iteration, you only need to check it when the window size increases when you increase the index of right, correct? There’s no need to check when you decrease the window size since you know it’ll be getting smaller than whatever the previous longest size is.

12

tru, no harm in putting longest = max(longest, r - l) at the end of both branches tho. if there’s no increase then it’s just no op.

14

Using a hashmap that holds character and its last occurrence instead of a set makes it more efficient. That way, we need to not skip one character at a time but can directly skip to the index where the duplicate was occurred last. Here’s a snippet.

    int windowStart = 0, maxLength = 0;
    //Map to hold character and its latest index
    Map<Character, Integer> map = new HashMap<>();
    for(int windowEnd = 0; windowEnd < s.length(); windowEnd++) {
        char rightChar = s.charAt(windowEnd);
        
        if(map.containsKey(rightChar)) {
            windowStart = Math.max(windowStart, map.get(rightChar) + 1);
        }
        
        map.put(rightChar, windowEnd);
        
        maxLength = Math.max(maxLength, windowEnd - windowStart + 1);
    }
    
    return maxLength;
15

/*
Using a for loop for the r pointer.
*/

function longestSubstringWithoutRepeatingCharacters(s) {
const seen = new Set();
let l = 0;
let maxLength = 0;

for(let r = 0; r < s.length; r++) {
    const char = s.charAt(r);
    while(seen.has(char)) {
        seen.delete(s.charAt(l));
        l += 1;
    }
        
    seen.add(char);
    maxLength = Math.max(maxLength, r - l + 1)           
}

return maxLength;

}

16

LC: https://leetcode.com/problems/longest-substring-without-repeating-characters/

17

I see you using for loops and sometimes while loops. How do you decide which to use on sliding windows?

18

Is there a way to look at a question and easily tell if it can be solved with while loop or for loop? for example a double pointer sliding window will likely be a while loop, a double pointer same direction will likely be a for loop etc?

19

If you don’t need the index: use for-in loop
If you need to access each element: use for loop with index
else (i.e. you may skip some elements): use while loop

For loops are easier to reason cuz the condition is predictable.

Thanks for bringing this up. This is a common question and we will write an article on it.

20

Like! It confuses me sometimes. I think for dynamic sliding window questions, a common pattern I’ve noticed is that you a for loop to move your window end, and then you use a while loop to keep adjusting the size of your window start.

def longest_substring_without_repeating_characters(s: str) → int:
longest = 0
window = {}
window_start = 0

for window_end in range(len(s)):
    curr_char = s[window_end]
    char_count = window.get(curr_char, 0)
    window[curr_char] = char_count + 1

    while window.get(curr_char) > 1:
        start_char = s[window_start]
        start_char_count = window.get(start_char, 0)
        window[start_char] = start_char_count - 1
        window_start = window_start + 1

    curr_longest = window_end - window_start + 1
    longest = max(longest, curr_longest)
return longest
21

In the implementation block, the longest length of the substring is equal to righter pointer minus left pointer plus one.
incorrect → Line 13 → longest = max(longest, r - l)
correct → Line 13 → longest = max(longest, r - l + 1)

22

Example illustration is wrong. ABCDE is subsequence not substring. The answer should be CDBEA.

23

Got it nvm. It shows the elements in Set.

24

you still to remove those letters from the set one a time tho

25

This is such a mindf9)&*(k… I couldn’t figure this out and solved with DP instead. How do people even come up with such solutions?

26

Simple C# Solution:
public static int LongestSubstringWithoutRepeatingCharacters(string s)
{
var set = new HashSet();
int l = 0, r = 0, length = 0;

    while(r < s.Length)
    {
        if (!set.Contains(s[r]))
        {
            set.Add(s[r]);
            length = Math.Max(length, set.Count);
            r++;
        }
        else
        {
            set.Remove(s[l]);
            l++;
        }
    }
    
    return length;
}