Longest Substring Without Repeating Characters

Problem:

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

Examples:

Given"abcabcbb", the answer is"abc", which the length is 3.

Given"bbbbb", the answer is"b", with the length of 1.

Given"pwwkew", the answer is "wke", with the length of 3. Note that the answer must be a substring, "pwke" is a subsequence and not a substring.

Constraints:

0 <= s.length() <= 5 * 10^4

Approach:

This problem can be solved using the "Two Pointers" method. Now the question is how can we move our pointers. We have to think a little bit, we can't sort our string or we can't take two pointers from 2 sides (left and right).

See, we can start our both pointers from starting position, every time we will increase one pointer, then if we met the current character before, then another pointer will be updated by the previous position of the current character. Okay, let's try to visualize,

Every time we will increase the right pointer, and at the same time, we will update our maximum length by (right - left + 1) and we will mark the current character position, if we see we have already met this character before, then simply we'll update left pointer by,

left = previous position + 1.
See the Code for a better understanding.

Time Complexity: O(n)

Space Complexity: O(1)