Longest Substring Without Repeating Characters | Brute Force Approach | Sliding Window Algorithm

Bruteforce Approach
The simplest approach to solve this problem is to generate all the substrings of the given string and among all substrings having all unique characters, return the maximum length.

Sliding WIndow Approach
In the previous naive approach, we need to repeatedly consider a substring and check if it contains a duplicate character. But due to this, we are performing some repeatable tasks which can be further improved, i.e., if a substring S[i][j] from index i to j – 1 has already been checked to have no duplicate characters, then simply check if S[j] is a substring of S[i][j].

Optimised Sliding Window
In the above approach, checking if the substring contains another string, takes O(N^2) time. But can it be improved?

Yes, using a HashSet as a sliding window, we can check if a character has already been visited and is present in the current window. It can be done in O(1).

The approach is to scan the string from left to right using two pointers left and right. It helps to keep a track of the maximum non-repeating substring in the string.

---------------------------------------- About SCALER --------------------------------------------------

A transformative tech school, creating talent with impeccable skills. Upskill and #CreateImpact

📌 Follow us on Social and be a part of an amazing tech community📌

🔔 Hit that bell icon to get notified of all our new videos 🔔

If you liked this video, please don't forget to like and comment. Never miss out on our exclusive videos to help boost your coding career! Subscribe to Scaler now!

#longestsubstring #bruteforce #slidingwindow #interview #coding