Optimizing String Substring Length With O(n) Time Complexity
Optimal approach to find longest substring without repeating chars: TC O(n), SC O(256) using int[] of size 256. Update left pointer when duplicate found, keep track of max window substring.
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.len...