3. Longest Substring Without Repeating Characters | LeetCode Medium | Python Solution | Two Pointer

Leetcode medium problem 3. Longest Substring Without Repeating Characters, detailed explanation and solution in python language.

LeetCode Problem Link: https://leetcode.com/problems/longest-substring-without-repeating-characters/
Solution (Python Code): https://github.com/shaheershukur/LeetCode-Python-Solutions/blob/main/Python%20Solutions/3.%20Longest%20Substring%20Without%20Repeating%20Characters.py

#leetcode #python #solution

Problem Statement:
Given a string s, find the length of the longest
substring
without repeating characters.
______________________________________________________________

LeetCode problem solving helps in improving one's problem solving and coding skills . Also, it helps in clearing technical interviews at top tech companies like Microsoft, Google, Amazon, Facebook, Walmart, Apple etc.
(FAANGM, MAANGM, Product based companies)

CC of video:
we are given a string, and we need to find out the length of the longest substring without repeating characters.
for example, if this is the given string, then the longest substring without repeating characters is this.

to solve this, we will use two pointers i and j.
one pointer to track the beginning of the substring.
and the other pointer to track the end of the substring.

with an example, lets see how we can find out the longest substring without repeating characters.
first we will place both the pointers i and j at the beginning of the string index 0.

we will be using the pointer j to visit each character in the string, and on visiting each character, we will be storing the index at which that character was found, in a dictionary.

here pointer j found the character x at index 0.
so we will store that information.

at this point, the number of characters between pointers i and j is 1.
so the longest substring without repeating characters is 1.

now, we will move the pointer j to the next character.
here, character y is found at index 1.
so we will store that information.

also, now the longest substring without repeating characters is 2.

now, we will move the pointer j to the next character.
here, character y is found at index 2.
but, if we look at the dictionary, we can see that this character was already found at index 1.

that means, between the pointers i and j, there are two y characters, and therefore we must move the pointer i to the maximum index up to which there are no repeating characters.
the pointer i is currently at index 0. the index at which the character y was previously found is 1. therefore we will move the pointer i to the maximum index without repeating characters, which is 2.

since pointer j has found a new index for the character y, we will update it in the dictionary.
and since the current length of the substring 1 is less than the previously found out longest substring, we dont have to update the maximum length.

now, we will move the pointer j to the next character.
here, character a is found at index 3.
so we will store that information in the dictionary.

now the longest substring without repeating characters is 2.

now, we will move the pointer j to the next character.
here, character b is found at index 4.
so we will store that information in the dictionary.

now there are 3 characters between i and j.
so the longest substring without repeating characters is 3.

now, we will move the pointer j to the next character.
here, character c is found at index 5.
so we will store that information in the dictionary.

now there are 4 characters between i and j.
so the longest substring without repeating characters is 4.

now, we will move the pointer j to the next character.
here, character x is found at index 6.
if we look at the dictionary, we have already found out the character x at index 0.
but the pointer i is already ahead of index 0 and at a maximum index at which there are no repeating characters.
therefore, in this case, we dont have to move the pointer i, and there are 5 characters between the pointers i and j.
so the longest substring without repeating characters is 5, and this is the final result we have.
now lets code the solution.
we will store the number of characters in the string in this variable.
if the number of characters are less than or equal to 1, then we dont have to do anything. we can directly return that length.
we will create this variable for storing the longest substring without repeating characters, and at last we will be returning it.
we will create two pointers i and j initially at index 0.
and also, for storing the index at which characters are found, we will create a dictionary.
now, we will use a while loop to move the pointer j through all the characters till the end of the string.
during each loop, we will store the index at which the character was found, in the dictionary.
also, we will check whether we have found out a new substring with maximum length.
we will then increment the pointer j to move to the next character.
and at the beginning of the loop.