Coding Interview AI

Approach: Use a sliding window technique with a hash map to track character positions.

Time Complexity: O(n) where n is the length of the string

Space Complexity: O(min(m, n)) where m is the size of the character set

Implementation:

function lengthOfLongestSubstring(s) {
  const charMap = new Map();
  let maxLength = 0;
  let windowStart = 0;
  
  for (let windowEnd = 0; windowEnd < s.length; windowEnd++) {
    const rightChar = s[windowEnd];
    
    // If character is already in current window, update window start
    if (charMap.has(rightChar) && charMap.get(rightChar) >= windowStart) {
      windowStart = charMap.get(rightChar) + 1;
    }
    
    // Update character position
    charMap.set(rightChar, windowEnd);
    
    // Update max length
    maxLength = Math.max(maxLength, windowEnd - windowStart + 1);
  }
  
  return maxLength;
}

Key Points to Explain:

• We use a Map to store the most recent position of each character
• The sliding window (windowStart to windowEnd) represents our current substring
• When we find a duplicate, we move the window start to just after the previous occurrence
• We continuously update the maximum length as we go