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)