Given a String find a longest substring without repeating characters
seenhar[urrenthar]={a,b,d}
Example 1:
Input: s = "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.
Example 2:
Input: s = "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.
Example 3:
Input: s = "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3.
Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.
Explanation
coming up with brute force methods
abcbdca
{a} longest substring=1
{a,b} longest substring=2
{a,b,c} longest substring=3
{a,b,c,b}= {b} longest substring=1// since b is already appeared
{b,d} longest substring=2
{b,d,c} longest substring=3
{b,d,c,a} longest substring=4
Verify constraints
Is the substring contiguous
yes ,look for substring not a subsequence
coding out through brute force solution
"abccabb"
const length of Longest Substring=function(s){
if(s.length<=1){
return s.length;
}
let longest=0;
for(let left=0;left<s.length;left++)
{
let seenchar={},currentLength=0;
for(let right=left;right<s.length;right++)
{
const currentchar=s[right];
if(!seenchar[currentchar]){
currentLength++;
seenchar[currentchar]=true;
longest=Math.max(longest,currentLength);
}
else
{
break;
}
}
}
return longest;
}
Explanation
if(s.length<=1){
return s.length;
}
if only a is there
ex: a
a==>s.length<=1==>1<=1===>return s.length==1
for(let right=left;right<s.length;right++)
{
const currentchar=s[right];
if(!seenchar[currentchar]){
currentLength++;
seenchar[currentchar]=true;
longest=Math.max(longest,currentLength);
}
eg:abcbda
a b c b d a
L
R
currentchar=s[right]=a
seenchar={a}
if(!seenchar[currentchar])
currentLength++;===>1
seenchar[currentchar]=true;
longest=Math.max(longest,currentLength);===>(0,1)=1
right++
a b c b d a
L
R
currentchar=s[right]=b
seenchar={a b}
if(!seenchar[currentchar])
currentLength++;===>2
seenchar[currentchar]=true;
longest=Math.max(longest,currentLength);===>(1,2)=2
right++
a b c b d a
L
R
currentchar=s[right]=c
seenchar={a b c}
if(!seenchar[currentchar])
currentLength++;===>3
seenchar[currentchar]=true;
longest=Math.max(longest,currentLength);===>(2,3)=3
right++
a b c b d a
L
R
if(!seenchar[currentchar]) not works
so break
currentchar=s[right]=b
currentchar=s[right]=b
seenchar={ b }
if(!seenchar[currentchar])
currentLength++;===>1
seenchar[currentchar]=true;
longest=Math.max(longest,currentLength);===>(0,1)=1
right++
a b c b d a
L
R
currentchar=s[right]=d
seenchar={ b d}
if(!seenchar[currentchar])
currentLength++;===>2
seenchar[currentchar]=true;
longest=Math.max(longest,currentLength);===>(1,2)=2
right++
a b c b d a
L
R
currentchar=s[right]=a
seenchar={ b d a}
if(!seenchar[currentchar])
currentLength++;===>3
seenchar[currentchar]=true;
longest=Math.max(longest,currentLength);===>(2,3)=3
python solution without seeing the solution video:
class Solution:
def longest_substring_optimized(self, str):
# Use a sliding window technique
# Initialize left and right pointer to 0
# move right to forward, and if char not found in hash. Each iteration, compute
# right - left to compute the max_length.
# Now, if we find a character already found in hash, then check if the index of the character lies outside of left
# if yes, then we change the index value in the hash, else, we adjust the left pointer to the next of the found index
# of the duplicate char we just found.
left = 0
right = 0
hash_by_char = {}
max_length = 0
while right <= len(str) - 1:
if right - left > max_length:
# Do not do right - left + 1 to compute max_length, as we have already added +1 and then checked here,
# so, implicitly it adds +1
max_length = right - left
char = str[right]
if char not in hash_by_char:
hash_by_char[char] = right
right += 1
continue
else:
# check if already found character is out of our sliding window, if yes, then just update the hash
found_index = hash_by_char[char]
if found_index >= left:
left = found_index + 1
hash_by_char[char] = right
# Move right pointer to 1 ahead
right += 1
# check for the last one, as we broke the while loop, so we did not calculate the last max_count
if right - left > max_length:
max_length = right - left
return max_length
python3 solution (since you can't set prevSeenChar if currentChar has not been set in the seen hashmap/dict)
def lengthOfLongestSubstring(s: str) -> int:
#fast fail
if len(s) <= 1:
return len(s)
longest = 0
left = 0
seenChars = {}
for right in range(0,len(s)):
currChar = s[right]
prevSeenChar = -1
if currChar in seenChars.keys():
prevSeenChar = seenChars[currChar]
if prevSeenChar >= left:
left = prevSeenChar+1
seenChars[currChar] = right
longest = max(longest,right-left+1)
return longest
Top comments (0)