Coding Interview Questions | Longest Substring Without Repeating Characters

January 9th, 2024

Longest Substring Without Repeating Characters Problem Introduction:

This summary will talk about my solution to the longest substring without repeating characters problem as seen on leetcode here.

How do you solve the Longest Substring Without Repeating Characters Problem in O(n) time?

Solution:

function lengthOfLongestSubstring(s: string): number {
  let maxLength = 0;
  let left = 0;
  const charIndexMap = new Map<string, number>();

  for (let right = 0; right < s.length; right++) {
    const currentChar = s[right];

    if (
      charIndexMap.has(currentChar) &&
      charIndexMap.get(currentChar)! >= left
    ) {
      // If the current character is repeated and its last occurrence is within the current window,
      // move the left pointer to the right of the last occurrence.
      left = charIndexMap.get(currentChar)! + 1;
    }

    charIndexMap.set(currentChar, right);
    maxLength = Math.max(maxLength, right - left + 1);
  }

  return maxLength;
}

Longest Substring Without Repeating Characters Solution Summary:

Below is a breakdown of the key aspects of the solution above:

  1. Sliding Window Technique: The algorithm above employs the sliding window technique with two pointers, left and right, to iterate through the string while avoiding repeated characters in the current substring.
  2. Character Index Map: We use a Map (charIndexMap) to store the last index of each character encountered during the iteration. This map helps in efficiently updating the left pointer when a repeated character is found within the current window.
  3. Dynamic Window Adjustment: When a repeated character is encountered, and its last occurrence is within the current window (>= left), the left pointer is adjusted to the right of the last occurrence, ensuring a unique substring.
  4. MaxLength Calculation: The maximum length of the unique substring is continuously updated by comparing the length of the current window (right - left + 1) with the current maxLength.

Complexities:

  1. Time Complexity: The time complexity of the solution is O(n), where n is the length of the input string. The algorithm iterates through the string only once.
  2. 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. The space required for charIndexMap is determined by the character set’s size or the length of the input string, whichever is smaller. If the character set space is contained to a variant of only lower or upper case letters, the space complexity would be constant at O(1) as the maximum character space would be 26 or 52 characters, respectively, which are constants.