- Problem Statement
- Bruteforce Approach
- C++ Implementations of Bruteforce Approach
- Java Implementations of Bruteforce Approach
- Python Implementations of Bruteforce Approach
- Sliding WIndow Approach
- Optimised Sliding Window
- C++ Code For Optimised Sliding Window
- Java Code For Optimised Sliding Window
- Python Code For Optimised Sliding Window
- Practice Question
- Frequently Asked Questions

## 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:**

### Confused about your next job?

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