Longest substring without repeating characters

Problem

Brute force approach will involve creating all the possible substrings of the given string and finding out which one is the longest substring without the repeating character. This will lead to TC:O(n^2)

Optimal approach:
TC : O(n)
SC : O(256), for using int[] of size 256

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int hash[] = new int[256];// size of all the ascii characters
        Arrays.fill(hash,-1); // -1 to indicate these indexes don't have any character visited already
        int left =0,right =0;
        int max = 0;
        while(right<s.length()){
            char  c = s.charAt(right);
            if(hash[c]!=-1){// means the character has been seen in the past
                if(hash[c]>=left){// if the index of the character seen in the past is after the left pointer, then left pointer should be updated, to avoid duplicate in the window of substring
                    left  = hash[c] + 1;// has to be 1 index after the index of last seen duplicate character
                }
            }
            max = Integer.max(max, right-left+1);// keep track of mas window substring
            hash[c]  = right;// update the character last seen index in hash
            right++;
        }
        return max;
    }
}

The above is the detailed content of Longest substring without repeating characters. For more information, please follow other related articles on the PHP Chinese website!