**Problem Statement:** Given a String, find the length of longest substring without any repeating character.

**Examples:**

Example 1:Input:s = ”abcabcbb”Output:3Explanation:The answer is abc with length of 3.Example 2:Input:s = ”bbbbb”Output:1Explanation:The answer is b with length of 1 units.

**Solution**

** Disclaimer**:

*Don’t jump directly to the solution, try it out yourself first.*

**Solution 1: Brute force Approach**

**Approach**: This approach consists of taking the two loops one for traversing the string and another loop – nested loop for finding different substrings and after that, we will check for all substrings one by one and check for each and every element if the element is not found then we will store that element in HashSet otherwise we will break from the loop and count it.

**Code:**

## C++ Code

```
#include<bits/stdc++.h>
using namespace std;
int solve(string str) {
int maxans = INT_MIN;
for (int i = 0; i < str.length(); i++) // outer loop for traversing the string
{
unordered_set < int > set;
for (int j = i; j < str.length(); j++) // nested loop for getting different string starting with str[i]
{
if (set.find(str[j]) != set.end()) // if element if found so mark it as ans and break from the loop
{
maxans = max(maxans, j - i);
break;
}
set.insert(str[j]);
}
}
return maxans;
}
int main() {
string str = "takeUforward";
cout << "The length of the longest substring without repeating characters is " <<
solve(str);
return 0;
}
```

**Output:** The length of the longest substring without repeating characters is 9

**Time Complexity: **O( N^{2 })

**Space Complexity: **O(N) where N is the size of HashSet taken for storing the elements

## Java Code

```
import java.util.*;
public class Main {
static int solve(String str) {
int maxans = Integer.MIN_VALUE;
for (int i = 0; i < str.length(); i++) // outer loop for traversing the string
{
Set < Character > se = new HashSet < > ();
for (int j = i; j < str.length(); j++) // nested loop for getting different
string starting with str[i]
{
if (se.contains(str.charAt(j))) // if element if found so mark it as ans
and break from the loop
{
maxans = Math.max(maxans, j - i);
break;
}
se.add(str.charAt(j));
}
}
return maxans;
}
public static void main(String args[]) {
String str = "takeUforward";
System.out.println("The length of the longest substring without repeating
characters is " + solve(str));
}
}
```

**Output:** The length of the longest substring without repeating characters is 9

**Time Complexity: **O( N^{2 })

**Space Complexity: **O(N) where N is the size of HashSet taken for storing the elements

**Solution 2: Optimised Approach 1**

**Approach**: We will have two pointers left and right. Pointer ‘left’ is used for maintaining the starting point of substring while ‘right’ will maintain the endpoint of the substring.’ right’ pointer will move forward and check for the duplicate occurrence of the current element if found then ‘left’ pointer will be shifted ahead so as to delete the duplicate elements.

**Code:**

## C++ Code

```
#include <bits/stdc++.h>
#include<unordered_set>
using namespace std;
int solve(string str) {
int maxans = INT_MIN;
unordered_set < int > set;
int l = 0;
for (int r = 0; r < str.length(); r++) // outer loop for traversing the string
{
if (set.find(str[r]) != set.end()) //if duplicate element is found
{
while (l < r && set.find(str[r]) != set.end()) {
set.erase(str[l]);
l++;
}
}
set.insert(str[r]);
maxans = max(maxans, r - l + 1);
}
return maxans;
}
int main() {
string str = "takeUforward";
cout << "The length of the longest substring without repeating characters is " <<
solve(str);
return 0;
}
```

**Output:** The length of the longest substring without repeating characters is 9

**Time Complexity: **O( 2*N^{ }) (sometimes left and right both have to travel complete array)

**Space Complexity: **O(N) where N is the size of HashSet taken for storing the elements

## Java Code

```
import java.util.*;
public class Main {
static int solve(String str) {
int maxans = Integer.MIN_VALUE;
Set < Character > set = new HashSet < > ();
int l = 0;
for (int r = 0; r < str.length(); r++) // outer loop for traversing the string
{
if (set.contains(str.charAt(r))) //if duplicate element is found
{
while (l < r && set.contains(str.charAt(r))) {
set.remove(str.charAt(l));
l++;
}
}
set.add(str.charAt(r));
maxans = Math.max(maxans, r - l + 1);
}
return maxans;
}
public static void main(String args[]) {
String str = "takeUforward";
System.out.println("The length of the longest substring without repeating
characters is " + solve(str));
}
}
```

**Output:** The length of the longest substring without repeating characters is 9

**Time Complexity: **O( 2*N^{ }) (sometimes left and right both have to travel complete array)

**Space Complexity: **O(N) where N is the size of HashSet taken for storing the elements

**Solution 3: Optimised Approach 2**

**Approach:** In this approach, we will make a map that will take care of counting the elements and maintaining the frequency of each and every element as a unity by taking the latest index of every element.

**Code:**

## C++ Code

```
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int lengthofLongestSubstring(string s) {
vector < int > mpp(256, -1);
int left = 0, right = 0;
int n = s.size();
int len = 0;
while (right < n) {
if (mpp[s[right]] != -1)
left = max(mpp[s[right]] + 1, left);
mpp[s[right]] = right;
len = max(len, right - left + 1);
right++;
}
return len;
}
};
int main() {
string str = "takeUforward";
Solution obj;
cout << "The length of the longest substring without repeating characters is " << obj.lengthofLongestSubstring(str);
return 0;
}
```

**Output:** The length of the longest substring without repeating characters is 9

**Time Complexity: **O( N^{ })

**Space Complexity: **O(N) where N represents the size of HashSet where we are storing our elements

## Java Code

```
import java.util.*;
public class Main {
static int solve(String s) {
HashMap < Character, Integer > mpp = new HashMap < Character, Integer > ();
int left = 0, right = 0;
int n = s.length();
int len = 0;
while (right < n) {
if (mpp.containsKey(s.charAt(right))) left = Math.max(mpp.get(s.charAt(right)) + 1, left);
mpp.put(s.charAt(right), right);
len = Math.max(len, right - left + 1);
right++;
}
return len;
}
public static void main(String args[]) {
String str = "takeUforward";
System.out.println("The length of the longest substring without repeating
characters is " + solve(str));
}
}
```

**Output:** The length of the longest substring without repeating characters is 9

**Time Complexity: **O( N^{ })

**Space Complexity: **O(N) where N represents the size of HashSet where we are storing our elements

Special thanks toplease check out this articleGurmeet Singhfor contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam,