algoadvance

Leetcode 3. Longest Substring Without Repeating Characters

Problem Statement

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

Clarifying Questions

  1. Input Constraints: What are the constraints on the input string s?
    • Typically, the length of s is between 0 and 5 * 10^4.
  2. Character Set: Are the characters in s only ASCII?
    • Assume s contains ASCII characters.
  3. Case Sensitivity: Is the substring case-sensitive?
    • Yes, ‘A’ and ‘a’ are different characters.

Strategy

The optimal approach to solve this problem is to use the sliding window technique along with a hash map to keep track of the characters and their indices within the current window. The sliding window will help us efficiently keep track of the longest substring without repeating characters by expanding and contracting as needed.

Steps

  1. Initialize two pointers (left and right) for the sliding window, both starting at the beginning of the string.
  2. Use a hash map to store characters and their most recent indices.
  3. Traverse through the string with the right pointer.
    • If a character has already been seen (exists in the hash map):
      • Move the left pointer right beyond the last occurrence of that character to ensure no repeating characters within the current window.
    • Always update the hash map with the current character’s latest index.
    • Calculate the length of the current window and update the maximum length accordingly.
  4. Return the length of the longest substring found.

Code

#include <iostream>
#include <unordered_map>
#include <algorithm>
#include <string>

int lengthOfLongestSubstring(std::string s) {
    std::unordered_map<char, int> charIndexMap;
    int maxLength = 0;
    int left = 0;
    
    for (int right = 0; right < s.size(); ++right) {
        if (charIndexMap.find(s[right]) != charIndexMap.end()) {
            // Move left pointer to the right of the first occurrence of s[right]
            left = std::max(charIndexMap[s[right]] + 1, left);
        }
        // Update the most recent index of s[right]
        charIndexMap[s[right]] = right;
        // Calculate the length of the current window
        maxLength = std::max(maxLength, right - left + 1);
    }
    
    return maxLength;
}

// Test Example
int main() {
    std::string s = "abcabcbb";
    int length = lengthOfLongestSubstring(s);
    std::cout << "Length of the longest substring without repeating characters: " << length << std::endl;
    return 0;
}

Time Complexity

The time complexity of this approach is O(n), where n is the length of the string s. This is because each character is processed at most twice (once by the right pointer and once by the left pointer). The space complexity is O(min(m, n)) for the hash map, where m is the size of the character set, and n is the length of the string s. For ASCII characters, this is effectively O(1).

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI