Longest Substring Without Repeating Characters


Difficulty Level Medium
Frequently asked in Adobe Alation Amazon Apple Bloomberg ByteDance Cisco eBay Expedia Facebook Goldman Sachs Google Microsoft Morgan Stanley Oracle SAP SAP Labs Spotify Uber VMware Yahoo
Hash Hashing Sliding Window String Two Pointer

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

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
            {
             hash.add(s.charAt(j));
             j=j+1;
             max=Math.max(j-i,max);   
            }
        }
        return max;
    }
}

class Main{
  public static void main(String[] args){
    int answer = (new Solution()).lengthOfLongestSubstring("pwwkew");
    System.out.print(answer);
  }
}
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){
    int answer = (new Solution()).lengthOfLongestSubstring("abcdefg");
    System.out.print(answer);
  }
}
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