Home » Technical Interview Questions » String Interview Questions » Longest Substring Without Repeating Characters

# Longest Substring Without Repeating Characters

Difficulty Level Easy

Given a string, we have to find the length of the longest substring without repeating characters.

Let’s look into a few examples:

## Example

`pwwkew`
`3`

Explanation: Answer is “wke” with length 3

`aav`
`2`

Explanation: Answer is “av” with length 2

## Approach-1 for Longest Substring Without Repeating Characters

### Brute Force

Checking all the substrings one be one for duplicate characters

• Time Complexity
• Number of strings that will be formed =n*(n+1)/2
• Time is taken to check each string=O(n)
• Thus time complexity = O(n^3)
• Space Complexity
• Storage of occurring characters for checking the uniqueness=n
• Thus Space Complexity=O(n)

## Approach-2 for Longest Substring Without Repeating Characters

### Sliding Window

We now keep track of the maximum length substring with no repeating characters.

• Let the maximum length be max which is initialised with 0
• We ensure that from  i to j-1 is already checked
• Every time we encounter a jth character
• If s[j] is not repeated
• It can be added to the substring
• The length of the substring can be increased
• j can be incremented
• s[j] can be recorded/added into the HashSet
• If s[j] is repeated
• We remove characters
• The starting point i.e i need to be changed
• We do this until the substring becomes repetition free

#### Java Program

```import java.util.*;
class Solution
{
public int lengthOfLongestSubstring(String s)
{
int max=0;
HashSet<Character>hash=new HashSet<Character>();
int i=0;
int j=0;
while(i<s.length() && j<s.length())
{
if(hash.contains(s.charAt(j)))
{
hash.remove(s.charAt(i));
i=i+1;
}
else
{
j=j+1;
max=Math.max(j-i,max);
}
}
return max;
}
}

class Main{
public static void main(String[] args){
}
}```
`pwwkew`
`3`

#### C++ Program

```class Solution
{
public:
int maxs(int a,int b)
{
if(a>b)
return a;
else
return b;
}
public:
int lengthOfLongestSubstring(string s)
{
int max=0;
set<char>hash;
int i=0;
int j=0;
while(i<s.length() && j<s.length())
{
if(hash.count(s[j]))
{
hash.erase(s[i]);
i=i+1;
}
else
{
hash.insert(s[j]);
j=j+1;
max=maxs(j-i,max);
}
}
return max;
}
};```
`pwwkew`
`3`

#### Complexity Analysis

Time complexity: O(n)

Space complexity: O(k) where k is the size of the sliding window

## Approach-3 for Longest Substring Without Repeating Characters

### Optimized Sliding Window

In the above approach, we keep removing characters and changing the start of the string until we come across the repeated character.

A hashmap can be used to keep the last occurrence of the repeating_character and i(the start of the substring) can be moved to that point making it an O(1) operation.

#### Java Program

```import java.util.*;
class Solution
{
public int lengthOfLongestSubstring(String s)
{
int max=0;
HashMap<Character,Integer>hash=new HashMap<Character,Integer>();
int i=0;
int j=0;
while(j<s.length())
{
if(hash.containsKey(s.charAt(j)))
{
i=Math.max(hash.get(s.charAt(j)),i);
}
hash.put(s.charAt(j),j+1);
max=Math.max(j-i+1,max);
j=j+1;
}
return max;
}
}

class Main{
public static void main(String[] args){
}
}```
`abcdefg`
`7`

#### C++  Program

```class Solution
{
public:
int maxs(int a,int b)
{
if(a>b)
return a;
else
return b;
}
public:
int lengthOfLongestSubstring(string s)
{
int max=0;
map<char,int>hash;
int i=0;
int j=0;
while(j<s.length())
{
if(hash.count(s[j]))
{
i=maxs(hash[s[j]],i);
}
hash[s[j]]=j+1;
max=maxs(j-i+1,max);
j=j+1;
}
return max;
}
};```
`aabbccddee`
`2`

#### Complexity Analysis

Time complexity: O(n)

Space complexity: O(k) where k is the size of the sliding window

References

 Array Interview Questions Graph Interview Questions LinkedList Interview Questions String Interview Questions Tree Interview Questions