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; } } 
Top comments (0)