# Longest Substring Without Repeating Characters LeetCode Solution

Difficulty Level Medium
Frequently asked in Adobe Alation Amazon Apple Bloomberg ByteDance Cisco DocuSign eBay Expedia Facebook Goldman Sachs Google Microsoft Morgan Stanley Oracle PayPal SAP SAP Labs ServiceNow Spotify Uber VMware Walmart Labs Yahoo Yandex Zillow Zoho
Hash Hashing Sliding Window String Two PointerViews 5922

Longest Substring Without Repeating Characters LeetCode Solution – 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 maxim
• um 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 for Longest Substring Without Repeating Characters LeetCode Solution

```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

Translate »