Longest Substring Without Repeating Characters 🧠

LeetCode Link: Longest Substring Without Repeating Characters

Difficulty: Medium

Problem Explanation 📝

Problem: LeetCode 3 - Longest Substring Without Repeating Characters

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

Intuition: To find the longest substring without repeating characters, we can use a sliding window approach. We can maintain a window that contains unique characters and keep expanding it until we encounter a repeating character. At each step, we update the maximum length of the non-repeating substring.

Approach:

1. Initialize variables left and right to represent the left and right pointers of the sliding window.

• Set both left and right to 0 initially.

2. Initialize a variable maxLen to store the maximum length of the non-repeating substring.
3. Initialize a set or map to keep track of the unique characters in the window.
4. Iterate while right is less than the length of the string:

• Check if the character at right is already present in the set/map:
• If it is present, remove the character at left from the set/map and increment left.
• If it is not present, add the character at right to the set/map, calculate the current length of the non-repeating substring as right - left + 1, and update maxLen if necessary.
• Increment right to expand the window.

5. Return maxLen, which represents the length of the longest substring without repeating characters.

⌛ Time Complexity: The time complexity is O(n), where n is the length of the input string. We iterate through the string once with the sliding window approach.

💾 Space Complexity: The space complexity is O(min(n, m)), where n is the length of the input string and m is the size of the character set. In the worst case, the character set can be as large as the input string, but it can also be limited by the number of distinct characters.

Solutions 💡

Cpp 💻

class Solution {
  public:
    int lengthOfLongestSubstring(string s) {
        int left = 0, right = 0;
        int maxLen = 0;
        unordered_set<char> charSet;

        while (right < s.length()) {
            if (charSet.count(s[right])) {
                charSet.erase(s[left]);
                left++;
            } else {
                charSet.insert(s[right]);
                maxLen = max(maxLen, right - left + 1);
                right++;
            }
        }

        return maxLen;
    }
};

/*
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int n = s.length();
        int ans = 0;
        vector<int> M(256, -1);
        int start = 0, end = 0;
        while(end < n) {
            if(M[s[end]] != -1) {
                start = max(start, M[s[end]] + 1);
            }
            M[s[end]] = end;
            ans = max(ans, end-start + 1);
            end++;
        }
        return ans;
    }
};
*/

Python 🐍

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        left, right = 0, 0
        max_length = 0
        unique_chars = set()

        while right < len(s):
            if s[right] not in unique_chars:
                unique_chars.add(s[right])
                max_length = max(max_length, right - left + 1)
                right += 1
            else:
                unique_chars.remove(s[left])
                left += 1

        return max_length