3. Longest Substring Without Repeating Characters

📝 Problem Details

• Title: 3. Longest Substring Without Repeating Characters
• Link: https://leetcode.com/problems/longest-substring-without-repeating-characters/
• Difficulty: Medium
• Tags/Categories: Sliding-Window Hashmap

input string s find the length of the longest substring without duplicate characters

💡 Explanation of Solution

Sliding Window Approach:

1. init two pointers:
	- left = 0 --> marks the start of the window
	- right = 0 --> expands the window
	- maxSubstr = 0 --> stores the max length of a substring found

2. use a hashset (uniqueChars) to keep track of characters in the current window

3. expand the window (right pointer)
	- if s[right] is already in the set, shrink the window from the left until s[right] can be included
	- otherwise, add s[right] to the set and update maxSubstr

⌛ Complexity Analysis

Time Complexity: O(n)
Space Complexity: O(26) --> O(1)

💻 Implementation of Solution

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int left = 0;
        int maxSubstr = 0;
        unordered_set<char> uniqueChars;
 
        for (int right = 0; right < s.size(); right++) {
            // If a duplicate character is found
            while (uniqueChars.find(s[right]) != uniqueChars.end()) {
                // Remove the character at the `left` pointer
                uniqueChars.erase(s[left]);
                // Move the `left` pointer to shrink the window
                left++;
            }
 
            // Add the current character to the set
            uniqueChars.insert(s[right]);
 
            // Update the maximum substring length
            maxSubstr = max(maxSubstr, right - left + 1);
        }
 
        return maxSubstr;
    }
};