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

Please click Like if you loved this article?

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
See also
Search in Sorted Rotated Array

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

See also
Count Pairs With Given Sum

References

Please click Like if you loved this article?