Longest Substring Without Repeating Characters LeetCode Solution

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:

Table of Contents

Example

pwwkew

Explanation: Answer is “wke” with length 3

aav

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

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

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

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