3. Longest Substring Without Repeating Characters

 

Longest Substring Without Repeating Characters

Problem Description

Given a string s, find the length of the longest substring without repeating characters.

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.

 

Constraints:

• 0 <= s.length <= 5 * 104
• s consists of English letters, digits, symbols, and spaces.

Idea:

1. Have two pointers that will define the current window's starting and ending indexes. Both will be 0 at the beginning.
2. Declare a Set that will store all the unique characters that we have encountered.
3. Declare a variable maxLength that will keep track of the length of the longest valid substring.
4. Scan the string from left to right one character at a time.
5. If the character has not been encountered before i.e., not present in the Set we will add it and increment the end index. The maxLength will be the maximum of Set.size() existing maxLength.
6. If the character has encountered it before, i.e., present in the Set, we will increment the start and we will remove the character at start index of the string.
7. Steps #5 and #6 are moving the window.
8. After the loop terminates, return maxLength.

Let`s code it!

A) Sliding Window

/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function(s) {
    const subArray = [];
    let counter = 0; 
    for(let i=0;i<s.length;i++){
        if(!subArray.includes(s[i])){
            subArray.push(s[i]);
            if(subArray.length > counter){
                counter = subArray.length;
            }
        }else{
            // remove till s[i] if match 
            let index = subArray.indexOf(s[i]);
            subArray.splice(0, index+1);
            subArray.push(s[i]);
        }
    }
    return counter;
};

B) Sliding With Set Approach:

/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function(s) {
    // Base condition
    if (!s) {
        return 0;
    }
    // Starting index of the window
    let start = 0;
    // Ending index of the window
    let end = 0;
    // Maximum length of the substring
    let maxLength = 0;
    // Set to store the unique characters
    const uniqueCharacters = new Set();
    // Loop for each character in the string
    while (end < s.length) {
        if (!uniqueCharacters.has(s[end])) {
            uniqueCharacters.add(s[end]);
            end++;
            maxLength = Math.max(maxLength, uniqueCharacters.size);
        } else {
            uniqueCharacters.delete(s[start]);
            start++;
        }
    }
    return maxLength;
}

Complexity 

Time Complexity
We are scanning the string from left to right only once, hence the time complexity will be O(n).


Space Complexity
We are using Set as a data structure to facilitate our computation, therefore, the space complexity should also be O(n), right? Wrong!

Conclusion

That’s all folks! In this post, we solved LeetCode problem #3. Longest Substring Without Repeating Characters using Sliding Window Technique.

I hope you have enjoyed this post. Feel free to share your thoughts on this.

You can find the complete source code on my GitHub repository. If you like what you learn. feel free to fork 🔪 and star ⭐ it.

In this blog, I have tried to solve leetcode questions & present the most important points to consider when improving Data structure and logic,  feel free to add, edit, comment, or ask. For more information please reach me here
Happy coding!