Leetcode 3) Longest Substring Without Repeating Characters

21 Apr 2021 in Algorithms

Sliding Window

class Solution {
    int real_max = 0;
    int start=0;
        
    public void count(int b, String s){
        for(int i=b-1;i>=start;i--){
            if(s.charAt(i)==s.charAt(b)){
                int max=b-1-start+1;
                if(real_max<max){
                    real_max=max;
                }
                start=i+1;
                break;
            }
        }               
    }

    public int lengthOfLongestSubstring(String s){
        if(s.length()<=1){
            return s.length();
        }
        int end=1; 
        while(end<s.length() && start<s.length()){
            count(end,s);
            end++;
        }
        //end
        int max= s.length()-start;
        if(max>real_max){
            real_max=max;
        }
            return real_max;
    } 
}

Different solution

• Easy example:
  • Array index 0 indicates A, index 1 indicates B …
  • if (start index) < (array stored value)
    • the character already exists in the sub string (redundancy is found)
    • set new start index as (array stored value+1)

class Solution {
    public int lengthOfLongestSubstring(String s) {
        if(s.isEmpty()) {
            return 0;
        }
        char[] array = s.toCharArray();
        int[] ascci = new int[128];
        //Initializing all values with -1.
        for(int i=0; i<ascci.length; i++) {
            ascci[i] = -1;
        }
        int startIndex = 0;
        int max = 0;
        //array contains all characters from given string.
        for(int i = 0; i < array.length; i++) {
            /*array[i] is a character, but it will typecast to ascci code number.
            ascci[] returns -1 or previous index of the character if it exists.*/
            
            //if prevIndex is -1, meaning that it never showed up before.
            int prevIndex = ascci[array[i]];
            ascci[array[i]] = i;
            
            //if(prevIndex >= startIndex)==true, meaning it is repeated character. 
            if(prevIndex >= startIndex) {
                //start again from the next character of repeated character.
                startIndex = prevIndex + 1;
            }
            //if new substring is longer than max, replace max length.
            if(i + 1 - startIndex > max) {
                max = i + 1 - startIndex;
            }
            //if max is longer than what it is left in array, then return and end. 
            if(array.length - startIndex <= max) {
                return max;
            }

        }
        return max;
    }
}

• Sliding Window

class Solution {
    public int lengthOfLongestSubstring(String s){
        int left =0; int right=0;
        Map<Character,Integer> chars = new HashMap<>();
        int max = 0;

        while( right < s.length()){
            char currentChar = s.charAt(right);
            if(!chars.containsKey(currentChar)){
                chars.put(currentChar,1);
                right++;
                max= Math.max(max,right-left);
            }else{
                //chars.remove(currentChar);
                chars.remove(s.charAt(left));
                left++;
            }
        }
        return max;
    }
}