Day 28: Longest Substring Without Repeating Characters: Sliding Window - leetcode - Python3

 Given a string s, find the length of the longest 

substring

 without repeating 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:

• 0 <= s.length <= 5 * 104
• s consists of English letters, digits, symbols and spaces.

 SOLUTION

class Solution:

    def lengthOfLongestSubstring(self, s: str) -> int:

        sSet: Set[T] = set()

        l: int = 0

        result: int = 0

        for r in range(len(s)):

            while s[r] in sSet:

                sSet.remove(s[l])

                l += 1

            sSet.add(s[r])

            result = max(result, r-l+1)

        return result

Time Complexity: O(n)

Space Complexity:O(n)

How it works:

1. The function lengthOfLongestSubstring takes a string as input and returns the length of the longest substring without repeating characters.
2. A set is created to store the characters in the substring.
3. Two pointers are initialized: l is the left pointer, and r is the right pointer.
4. The variable result is initialized to 0.
5. The loop iterates over the characters in the string.
6. If the current character is already in the set, the leftmost character from the set is removed.
7. The current character is added to the set.
8. The result is updated to the maximum of the result and the length of the substring from l to r.
9. The right pointer is incremented.
10. The loop continues until the right pointer reaches the end of the string.
11. The function returns the result.