Longest substring without repeating characters

Attempt 1 (didn’t work)

'''
approach:
dictionary can be used to keep track of unique char, O(1) lookup might make the program linear
whenever a duplicate char comes up, store the current string as longest string if its length is greater than previous string.
At the end of loop all charaters have been looped through and the result can be printed
 
puesdo code:
str = 'abcabcbbt'    
dict = {}
longest = 0
 
for s in str:
    if s in dict:
        longest = length(dict)
        dict = {}
        return
    
    dict[s] = 1
    
print(longest)
    
tc, sc:
    tc: n
    sc: n
'''
 
class Solution(object):
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        
        d = {}
        longest = 0
        ls = list(s)
        s_len = len(ls)
        # "pwwkew"
        for s in ls:
            if s in d:
                d = {}
                continue
 
            d[s] = 1
            if len(d) > longest:
                longest = len(d)
 
        print(longest)
        return longest
        

Attempt 2

• two_pointers

'''
approach:
have two pointers, first pointer starts with 0th index and second with 1st index, 
go through all the chars in string if the first and second pointer are containing same value 
then set the first pointer to second pointer location and second pointer + 1 postion, when this condition happens also store length of string or difference between second pointer - first pointer, compare with a variable that was initialted outside loop with 0 for max of second pointer - first pointer, previousMax.
return the value in end.
 
psuedo code:
str = ''
strAsArray = convert(str)
currentMax = 0
pointerOne = 0
pointerTwo = 1
dict = {}
dict[str[0]] = 1
dict[str[1]] = 1
for s, index in strAsArray:
    if s in dict:
        currentMax = max(pointerTwo - pointerOne, currentMax)
        pointerOne = pointerTwo
        pointerTwo = pointerTwo + 1
        dict = {}
        dict[s[pointerOne]] = 1
        dict[s[pointerTwo]] = 1
    else 
        pointerTwo += 1
        dict[s] = 1
        
return currentMax
    
    
dry run:
-------vv------
str = 'pwwkew'
first iteration:
    pointerOne at p, pointerTwo at w
    goes to else pointTwo becomes 2
second interation:
-------v-v---
str = 'pwwkew'
    my approach is wrong, duplicate char has come up but it is not equal to first 
    I need to use a dict to keep track of that
    now dict has alraedy w so it goes to if condition new max is 2 - 0 = 2 
    assigned to currentMax
    pointerOne is 2 now
    pointerTwo is 3
    dict is empty
third iteration:
pwwkew
--^^--
    these two chars need to be added to the dict now which is done, modified if condition
    comes to else pointerTwo becomes 4
    e gets added to dict
4th:
pwwkew
--^-^--
    else pointerTwo is 5 now
    e added to dict
pwwkew
--^--^
    w is in dict so if condition
    pointerTwo - pointerOne = 5-2 = 3
    currentMax = (3, 2) = 2
    pointerOne = 5
    pointerTwo = 6 (out of bounds)
    
    
 
tc, sc: 
O(n), O(1)
 
'''
class Solution(object):
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        strAsArray = list(s)
        currentMax = 0
        pointerOne = 0
        pointerTwo = 1
        dict = {}
        dict[strAsArray[0]] = 1
        dict[strAsArray[1]] = 1
        for index, c in enumerate(strAsArray):
            if c in dict:
                currentMax = max(pointerTwo - pointerOne, currentMax)
                pointerOne = pointerTwo
                pointerTwo = pointerTwo + 1
                dict = {}
                if pointerOne < len(strAsArray):
                    dict[strAsArray[pointerOne]] = 1
                if pointerTwo < len(strAsArray):
                    dict[strAsArray[pointerTwo]] = 1
            else:
                pointerTwo += 1
                dict[c] = 1
 
        return currentMax 

Attempt 3 ✅

class Solution {
    lengthOfLongestSubstring(s) {
        if (s.length === 0) {
            return 0;
        }
 
        let res = 1;
        let slow = 0;
        const charIndexMap = new Map();
 
        for (let i = 0; i < s.length; i++) {
            const char = s[i];
 
            if (charIndexMap.has(char) && charIndexMap.get(char) >= slow) {
                // If the character is already in the substring [slow:i],
                // update the slow pointer to the next position after the last occurrence of the character.
                slow = charIndexMap.get(char) + 1;
            }
 
            // Update the result by taking the maximum of the current result and the length of the current substring.
            res = Math.max(res, i - slow + 1);
 
            // Update the index of the current character in the hashmap.
            charIndexMap.set(char, i);
        }
 
        return res; // Return the final result.
    }
}
 
// Example usage
const solution = new Solution();
const result = solution.lengthOfLongestSubstring("abcabcbb");
console.log(`Length of the longest substring without repeating characters: ${result}`);
 

Python

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        if len(s) == 0:
            return 0
        res = 1
        slow = 0
        for i in range(1, len(s)):
		  cur_char = s[i]
		  slow_cur_substr = s[slow : i]
            if cur_char in slow_cur_substr:
                slow = slow_cur_substr.index(cur_char) + slow + 1
            res = max(res, i - slow + 1)
        return res
s = Solution()
print(s.lengthOfLongestSubstring('oneeasdfgh'))

Above returns 0 if s is 0. there are two more variables response is 1 and slow is 0 the for loop startsinitialization_phase has variables above and starts from 1 inmaintaince_phase if char is present in string between slow to current index then - slow pointer is updated to current index + slow + 1 then response is updated with the max between res and current_index - slow + 1 intermination_phase return the res In Javascript substring method can be used to perform the Python list, tuple operation.

approach:

psuedo code:

dry run:

tc, sc: