Learning Journal

2/23/2024

Longest Substring Without Repeating Characters - 3rd attemp

Tags: algorithms leetcode sliding_window

function lengthOfLongestSubstring(s: string): number {
    let start = 0, end = 0, max = 0;

    while(end < s.length){
        const curChar = s.charAt(end);

        const iCurChar = s.indexOf(curChar, start);

        if(iCurChar < end) {
            start = iCurChar + 1;
        }

        if(max < end - start + 1){
            max = end - start + 1;
        }

        end++;
    }

    return max;
};function lengthOfLongestSubstring(s: string): number {
    let start = 0, end = 0, max = 0;

    while(end < s.length){
        const curChar = s.charAt(end);

        const iCurChar = s.indexOf(curChar, start);

        if(iCurChar < end) {
            start = iCurChar + 1;
        }

        if(max < end - start + 1){
            max = end - start + 1;
        }

        end++;
    }

    return max;
};

THE PROBLEM

This is a different approach from my last two attempts. This time, I still use sliding window technique but with a little modification (and led to big improvement).

I still use start and end to mark the start and end index of the substring. However, I don't use hashTB to record the last occurence's position of the characters then move the start pointer to the next position after it when encountering a repeated character. Instead, I use the indexOf function of the string to determine if there is a repeated character. The indexOf function is much faster than the hash table.

Revised by ChatGPT

This approach utilizes the sliding window technique with a significant modification that leads to improved performance.

Instead of using a hash table to record the last occurrence's position of characters and then moving the start pointer to the next position after it when encountering a repeated character, this implementation leverages the indexOf function of the string. The indexOf function is used to determine if there is a repeated character within the current window. If a repeat is found, the start pointer is moved to the position right after the repeated character.

This change from using a hash table to relying on the indexOf function results in a faster solution, as indexOf is more efficient in this context. The algorithm maintains two pointers, start and end, to mark the boundaries of the current substring. The max variable is used to keep track of the length of the longest substring without repeating characters found so far. As the end pointer moves through the string, the algorithm continuously checks for repeats and updates the start pointer and max value accordingly.

Overall, this approach offers a more efficient solution to the problem of finding the length of the longest substring without repeating characters.