LeetCode 3| Longest Substring Without Repeating Characters | Medium

Problem

Given a string s, find the length of the longest substring without repeating characters.

ie. weqwjfd --> 4  (because wjfd is 4 chars)

Problem Analysis

1. String/Array
2. Find elastic string within substring
3. Though they asked to find the substring in examples they gave, they had the length of the largest substring
4. So, we need to return the length

Thinking about solution

1. We have a string we are going to need to scan it
2. Largest --> elastic find the boundaries of the string
3. Elastic + Array/String --> Sliding-Window == TwoPointers
4. But Sliding-Window

class Solution {

    public int lengthOfLongestSubstring(String s) {

        int l = 0;

        int result = 0;

        Set<Character> set = new HashSet<>();

        // We start with right pointer from 0, both left and right are at 0!.

        for (int r = 0; r < s.length(); r++) {

            // As long as we have duplicates move left first. Trick! at first 0,0 no duplicates!

            while (set.contains(s.charAt(r))) {

                set.remove(s.charAt(l)); // Note we remove what left points to! until we remove all duplicates with left.

                l++;

            }

            // Now add current different r into the set.

            set.add(s.charAt(r));

            // Trick! Note that when r = l = 0 then s is also empty and we would put in result 0 - 0 + 1 !

            result = Math.max(result, r - l + 1);

        }

        return result;

    }

}

The big question

1. The big question in this solution is when to extend the right pointer and when to extend the left
2. We basically always want to extend the right pointer
1. But if we are in a situation where we cannot extend the right pointer, we wont
2. i.e., if such a situation is that the character pointed by right pointer is already in the current string, we examine
3. We can know this by using a set
3. Our set will hold each character currently encountered by right
4. If right see that it's currently encountered char is not already in set then do not move right pointer to right
5. If our current right char is already in set, the left should move to the right
1. Until when left moves to the right? Until right not already in set
2. But the left will start moving to the right only when we face a situation where right sees that it already has a char in the set.