Longest Substring Without Repeating Characters

Problem Statement

Given a string S. The task is to find the length of the longest substring without repeating characters.

A substring is a contiguous sequence of characters within a string. For example – “view” is a substring of the string “Interviewbit”.

Examples:

Input: S = “abcabcbb”
Output: 3
Explanation:

“abc” is the longest substring without repeating characters among all the substrings.

Input:  S = “pwwkew”
Output: 3
Explanation:

“wke” is the longest substring without repeating characters among all the substrings.

---

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.

Algorithm

• To generate all substrings of a string, loop from the start till the end index of the string. Let us consider, the start index is i and the end index is j. Run a nested loop from i = 0 to N – 1 and j =  i + 1 till N. Hence, the substrings can be generated.
• To check if the substring contains all unique characters, put all the characters in the set one by one. If any of the characters are already present in the set, skip that string, else consider its length and maximize it.

C++ Implementations of Bruteforce Approach

Java Implementations of Bruteforce Approach

Python Implementations of Bruteforce Approach

Time Complexity: O(N^3), where N is the length of the string.
Space Complexity: O(min(N, M)), as HashSet is used. N is the length of the string and M is the size of the substrings.

---

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].

To check if a substring is present in another string can be done in O(N^2).

Image Source – Google Images

Algorithm:

• Run a loop from i = 0 till N – 1 and consider a visited array.
• Run a nested loop from j = i + 1 to N – 1 and check whether the current character S[j] has already been visited.
• If true, break from the loop and consider the next window.
• Else, mark the current character as visited and maximize the length as j – i + 1.
• Remove the first character of the previous window and continue.

C++ Code Sliding Window Method

Java Code Sliding Window Method

Python Code Sliding Window Method

Time Complexity: O(N^2), where N is the length of the string.
Space Complexity: O(min(N,M)), as a visiting array is used. N is the length of the string and M is the size of the substrings.

---

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.

Algorithm

• Initialise left = 0 and right = 0.
• Initialise a HashSet to store the characters of the current window.
• Slide the index right  toward N and if it is not present in the current HashSet, slide it further.
• Till this point, we have the maximum non repeating substring length.
• If a character is  found, which is present in the current window, remove the character from the current window and slide further.

C++ Code For Optimised Sliding Window

Java Code For Optimised Sliding Window

Python Code For Optimised Sliding Window

Time Complexity: O(N), where N is the length of the string.
Space Complexity: O(min(N,M)), as HashSet is used. N is the length of the string and M is the size of the substrings.

---

Practice Question

Longest Substring Without Repeat

---

Frequently Asked Questions

How to count occurrences of each character of a string?
The occurrence of each character can be found by considering a frequency array.

What is the approach used to find the length of the longest non-repeating substring?
Sliding Window is the most efficient approach to solve this problem.