## Debug School

rakesh kumar

Posted on • Updated on

# String:longest substring without repeat characters - brute force

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
``````