Longest Substring Without Repeating Characters

leetcode link

Given a string <span style="font-size: 0.75rem;">s</span>, find the length of the longest <span style="font-size: 14px;">substring</span> without duplicate characters.

Example 1:

Input: s = "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.

Example 2:

Input: s = "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.

Example 3:

Input: s = "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3.
Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.

Constraints:

• <span style="font-size: 14px;">0 <= s.length <= 5 * 10^4</span>

<span style="font-size: 14px;">s consists of English letters, digits, symbols and spaces.</span>

how to approach?

1. set the left pointer as 0, maxLength as 0, and also create the new Set to check the substring's element.

2. in for loop, set the right pointer which increment one by one to the right side of the given string.

3. in the for loop, set the while loop whenever the Set meets the duplicated element in the string then it will remove one by one from the left pointer and increment by 1 until there is no duplicated element in the set.

4. outside of while loop, inside for loop, the Set will add the element in s string with right pointer, and check the maxLength using Math.max method comparing existed max length of substring and the location of left pointer and right pointer by calculating them.

5. for loop is ended and the last maxLength value will be returned.

function lengthOfLongestSubstring(s: string): number {

    let subs = new Set();
    let left = 0;
    let maxLength = 0;

    for(let right=0;right<s.length;right++){
        while(subs.has(s[right])){
            subs.delete(s[left])
            left++
        }
        subs.add(s[right])
        maxLength = Math.max(maxLength,right - left +1)
    }

    return maxLength;
};

Summary

this leetcode problem is solved by typescript language.

the approach is setting two pointers from left to right and compare the max length of substring by moving the pointer one by one using Set concept of 'there is no duplicated element in Set.'.