Data Structures & Algorithms in Java – String – Longest Substring Without Repeating Characters

Problem:

Given a string , find the longest substring in the string without any repeating characters.

Example:

For the input abcabcbb , the longest substring is abc , so the output is 3

For the input dvdf , the longest substring is vdf , so the output is 3

Try out the solution here:

https://leetcode.com/problems/longest-substring-without-repeating-characters

Advertisements

Solution:

Hint:

  • Keep finding the length of substrings until you face a repeated character . This gives one of the substrings. Track its length. Find the first index of the repeated character and start finding the length again from the next character to that index. Keep tracking the length and record the maximum.

Example:

For the input “dvdf” ,

You start from the letter d , go to v

Then you find d again , the maximum length until now is 2.

Since you found a repeated letter (d) , Go back to the next letter of the previous d , that is to v again .

Start calculating the length again from v , this time you reach the end of the string without any repetition (“vdf”) , so length of the longest substring is 3.

ALGORITHM:

STEP 1: Initialize a string to store the longest substring

STEP 2: Initialize a variable to store the length of the longest substring

STEP 3: For every character in the string

STEP 3a: Check if the character is already in the substring we have calculated so far (initially this is empty as declared in STEP 1) . If so extract a substring from the substring starting from the next character to the given character. This is the new substring

STEP 3b: Append the new character to the substring (declared in STEP 1)

STEP 3c: Find the maximum of the substring lengths found out so far

STEP 4: Return the max length

Code:

class Solution {
public int lengthOfLongestSubstring(String s) {
  
    String test ="";
    
    int max = 0;
    
    
    for(char c: s.toCharArray()){
        
        
        if(test.contains(String.valueOf(c))){
            
            
            test = test.substring(test.indexOf(c)+1);
        }
        
        test = test.concat(String.valueOf(c));
        
        
        max = Math.max(max,test.length());
        
    }
    
    
    return max;
    
}
}

The time complexity of the above algorithm is O(n) and the space complexity is O(1).

Advertisements

There is another solution using external storage like hash map which can be used to store the index positions of each character.

Instead of finding if a character is found in a new substring and extracting a substring from the next character to it, we store the index positions of the characters and when a character is repeated we use a pointer to find out the next character to the repeated character’s first occurence.

Here is the code:

class Solution {
public int lengthOfLongestSubstring(String s) {
    

    
  
    var map = new HashMap<Character,Integer>();
    
    int max = 0,start = -1, current = 0;
    
    
    for(char c: s.toCharArray()){
        
   
        if(map.containsKey(c) && map.get(c) > start){
            
            
            start = map.get(c);
        }
        
        map.put(c,current);
        
        max = Math.max(max,current-start);
        
        current++;
        
    }
    
    
    return max;
    
}
}

We keep two pointers current and start.

current represents the current character that we are processing in the loop.

start represents the start of the longest substring. This is initialized to -1 since indexing starts at 0 in java and we want a pointer to point before that until we start executing our logic. (You can initialize to 1 as well with minor changes in the code)

We process each character and put its index position in a map.

We keep calculating the length until we face a repeated character.

When we face a repeated character , we look for its index in the map.

We point the start pointer to this index (this start pointer should be greater than the existing start position)

We calculate the length by finding the difference between the current pointer and the start.

Repeat this until the end of the string is reached and return the maximum length.

Time complexity is again O(n) since we iterate through the for loop for the length of the string.

Space complexity is O(n) since we store the index positions of all the characters in a hashmap for the worst case (all letters in the string are unique).

That’s it!

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s