Leetcode – 3 – Length of Longest Substring

Longest Substring Without Repeating Characters

Given a string, find the length of the longest substring without repeating characters. For example, the longest substring without repeating letters for “abcabcbb” is “abc”, which the length is 3. For “bbbbb” the longest substring is “b”, with the length of 1.

Description:

The problem is interesting that we have to find the substring from a given string until a point where you see a repeating characters adjacent to each other.

Brute Force Solution: (Having two loops)

We have to consider that the repeating characters may be adjacent to each other or it may be already visited. consider this input
abc – here the output should be 3
abccd- here we are seeing repeating characters as ‘cc’ so the substring of interest will be ‘abc’ , ‘bc’ and ‘cd’ – since abc is the max the output will be 3
abcdffghijkl – for this input the max will be 7 because we have to consider the substring ‘fghijkl’

With all this we can come up with

  • Having a loop to run along the length of the substring , i
  • Another loop to add the adjacent unique substring , j loop until repeating characters
  • return the count of substring with maximum length

Efficient Solution: (use only one loop)

We can reduce the runtime to visit the characters only once in the string and compute max as we go along

  • Have a running pointer which runs from 0 to length of the string
  • Have a boolean array to store the occurrence of character. the size will be 256 for ascii and 65536 for Unicode (we can confirm with the interviewer)
  • if the character is not seen till now, we set true at the corresponding ascii location in the boolean array, and increment our temporary max
  •  if not then we flip all the boolean and start form the next position along with storing the max to the result max
  • finally we will return the max of result max and temp max

1

Code:

public int lengthOfLongestSubstring(String s) {
        int running_head_pointer = 0;
        int head = 0;
        int result_max = 0;
        int temp_max = 0;
        boolean[] flagArray = new boolean[128];
        int length = s.length();
        
        char curr=' ';
        
        if(length == 0 || length == 1)
            return length;
        
        while(running_head_pointer < length){
            curr = s.charAt(running_head_pointer);
            
            if(!flagArray[curr]){
                flagArray[curr] = true;
                temp_max++;
                running_head_pointer++;
            }
            else{
                result_max = Math.max(result_max,temp_max);    
                temp_max=0;
                flagArray = new boolean[128];
                running_head_pointer = head + 1;
                head = running_head_pointer;
                }
                
            }
            return Math.max(result_max,temp_max);
        }

Time Complexity: O(n2)

  • we are simply iterating all the characters in a string and comparing adjacent characters O(n2)

Space Complexity:O(1)

  • storing in a boolean array for characters presence (max ascii – 256 or unicode – 65536) –O(1)
  • storing other values [max, pointer] – O(1)

Available Test Cases: 981

  • Check for null inputs
  • Check for no inputs
  • Check for repeating characters at the front, middle, end
  • Check for simple positive use case – [abcd]
  • Check for simple negative use case – [bb]
  • Check for combination of duplicates – [bbaaccdd]
  • Check with duplicates and sub strings – [bbabcdeffgdegg]
  • Check with sub strings without duplicates
  • Check for adjacent sub strings [abcdefghhijkkl]

 Github:

Leetcode_3_Length_of_longest_substring_non_repeating

 

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 )

Google photo

You are commenting using your Google 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

%d bloggers like this: