Leetcode - Longest Substring Without Repeating Characters

In this leetcode problem, we are asked to find the length of the longest string of characters in a provided string that does not contain repeating characters. In other words, in the string abcabcbb the longest substring without repeating characters is abc (with a length of 3).

Problem Statement

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.

          

Explanation

We can use two pointers to solve this problem.

Assign i = 0 and left = 0.
Create a set to keep track of characters in the substring.
Loop through the string

If the character at index i is not in the set, we add it to the set and increment i pointer.
If the character at index i is in the set, then we have found a new substring. We remove the character at index left from the set and increment left pointer.

Longest substring image

Complexity

Time Complexity is $$\mathcal{O}(n)$$, Space complexity is $$\mathcal{O}(1)$$