LeetCode - Longest Substring Without Repeating Characters

Hello, coding enthusiasts! 👋 Today, we’re going to unravel another intriguing problem from LeetCode: “Longest Substring Without Repeating Characters”.

Problem Statement

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

Constraints

0 <= s.length <= 5 * 10^4
s consists of English letters, digits, symbols and spaces.

Analysis

The task is to find the longest substring (a contiguous sequence of characters) in a given string that does not have any repeating characters.

Input: s = "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.

Approach

The sliding window approach is a perfect fit for this problem. Here’s how it works:

Initialize two pointers: These pointers represent the start and end of the sliding window.
Expand the window: Move the end pointer to the right and add the character to the window until we encounter a repeated character.
Shrink the window: Once we encounter a repeated character, move the start pointer to the right until the repeated character is removed from the window.
Keep track of the maximum length: During the process, keep updating the maximum length of the substring without repeating characters.

Time Complexity

The time complexity for this approach is O(n), where n is the length of the string. This is because we’re processing each character in the string once.

Space Complexity

The space complexity is O(min(m, n)), where m is the size of the charset. This is because we’re using a set to store the characters in the current window.

Code

Here’s the Python and JavaScript code for this approach:

Python

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        charset = set()
        l = 0
        maxLength = 0

        for r in range(len(s)):
            while s[r] in charset:
                charset.remove(s[l])
                l += 1
            charset.add(s[r])
            maxLength = max(maxLength, r - l + 1)

        return maxLength

JavaScript

var lengthOfLongestSubstring = function(s) {
    let charset = new Set();
    let l = 0;
    let maxLength = 0;

    for (let r = 0; r < s.length; r++) {
        while (charset.has(s[r])) {
            charset.delete(s[l]);
            l++;
        }
        charset.add(s[r]);
        maxLength = Math.max(maxLength, r - l + 1);
    }

    return maxLength;
};

Conclusion

In this post, we tackled the “Longest Substring Without Repeating Characters” problem from LeetCode using the sliding window approach. This solution has a time complexity of O(n) and a space complexity of O(min(m, n)).

Happy coding 😄

Learn More:

LeetCode – Longest Substring Without Repeating Characters