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

Longest Substring Without Repeating Characters


Reading Time - 3 mins


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
            {
             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)

READ  Top K Frequent Words

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

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