Longest Substring Without Repeating Characters

This is a popular coding problem often used in technical interviews to assess a candidate’s understanding of string manipulation and sliding window algorithms.

The goal of this problem is to find the length of the longest substring within a given string that does not contain any repeating characters.

Input: s = "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.

This problem can be efficiently solved using the “sliding window” technique. The idea is to maintain a sliding window (a substring) that contains only unique characters. As you iterate through the string, you expand the right end of the window when you encounter a new character and shrink the left end when you encounter a repeating character. Keep track of the maximum length of the window as you go.

Here’s a C++ solution:

#include <iostream>
#include <string>
#include <unordered_set>

using namespace std;

int lengthOfLongestSubstring(string s) {
  unordered_set<char> charSet;
  int maxLength = 0;
  int left = 0;

  for (int right = 0; right < s.length(); ++right) {
    while (charSet.count(s[right]) > 0) {
      charSet.erase(s[left]);
      left++;
    }
    charSet.insert(s[right]);
    maxLength = max(maxLength, right - left + 1);
  }

  return maxLength;
}

The time complexity of this solution is O(n), where n is the length of the input string. The algorithm iterates through the given string once, and during each iteration, it performs constant-time operations (inserting and erasing from the unordered set) to maintain the sliding window.

The space complexity is determined by the space used by the unordered set to store unique characters within the sliding window. In the worst case, the sliding window may contain all characters in the input string, so the space complexity is O(n). However, since the number of distinct characters in the set is limited (it’s the size of the character set, typically 256 for extended ASCII characters), the space complexity can be considered O(1) for practical purposes.