LeetCode — Longest Substring Without Repeating Characters

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

Photo by davide ragusa on Unsplash

Problem Description: Given a string s, find the length of the longest substring without repeating characters.

Example 1:
Input: s = "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.

Approach Used: Sliding window

Explanation: Since main aim in this question is to ensure there are no repeating characters in the substring, we need to check at each point if the current character is already there in the substring or not. If it is not there we simply include it in the substring, increase the length of the current substring by 1 and move ahead. This scenario will increase the size of our window. The other scenario will be when the current character is already in the substring. Since we want to find the longest substring with current character at each point we’ll remove the previous occurrence. But since a substring is continuous we will have to remove all the characters coming before the previous occurrence also. And then we can include the current character. This scenario will either decrease the size of our window or keep it the same if this character previously occurred as the first character of the substring.
We will need additional space to store the last occurrence of each character. Since we already know that there can be a certain number of characters only (128 in this case), we will make an array of a fixed size of 128. If a character is not found it’s the last index will be -1. Initially all characters will be -1, and after deletion also.

Code: (Java)

public int lengthOfLongestSubstring(String s) {
       
        //store last index of each character
        int[] alphabetLastIndex = new int[128];
        //intially all will ve -1, as none are found as of yet
        Arrays.fill(alphabetLastIndex, -1);
        
        //starting index of current substring
        int startingIndex=0;
        //length of current substring
        int length = 0;
        //maximum length substring found till that point
        int longestLength=0;
        
        for(int i=0; i<s.length(); i++){
            
            //if alphabet is already present in substring
            if(alphabetLastIndex[s.charAt(i)]!=-1){
                //store last occurence int temp variable
                //start of next substring will be 1 after this
                int temp = alphabetLastIndex[s.charAt(i)];
            
                //delete all character from starting index till previous occurence
                //of current character and recude length accordingly
                for(int j=startingIndex; j<=alphabetLastIndex[s.charAt(i)]; j++){
                    alphabetLastIndex[s.charAt(j)]=-1;
                    length--;
                }
                
                //start of next substring
                startingIndex = temp+1;
            }
            //update last index of current character
            alphabetLastIndex[s.charAt(i)]=i;
            //increase length after including current char
            length++;
            
            //update longest length if required
            if(length>longestLength)
                longestLength=length;
            
        }
        
        //return the longest length substring found in string
        return longestLength;
        
    }

Complexity:
Space complexity: O(1). Constant space of 128 required to store the last index of each character.
Time complexity: O(2n). In the worst scenario, each character will be visited twice. Once to add it to the substring, and once to remove it from the substring.

Note: This might not be the best solution. This is what I submitted and it got accepted.