This article explores different approaches to finding the longest substring within a given string that contains no repeating characters. We'll examine implementations using C++ and illustrate the underlying logic.

Sliding Window with unordered\_set

The first approach utilizes a sliding window technique, managed by an unordered\_set to keep track of characters currently within the window. The window expands to the right as long as no repeating characters are encountered. When a repeat is found, the left boundary of the window shifts to exclude the previous occurrence of the repeated character.

#include <string>
#include <unordered_set>
#include <algorithm>

class Solution {
public:
    int lengthOfLongestSubstring(std::string s) {
        std::unordered_set<char> window_chars;
        int n = s.length();
        int right_pointer = -1; // Initialize right pointer outside the string bounds
        int max_length = 0;

        for (int left_pointer = 0; left_pointer < n; ++left_pointer) {
            // If it's not the first iteration, remove the character at the previous left boundary
            if (left_pointer != 0) {
                window_chars.erase(s[left_pointer - 1]);
            }

            // Expand the window to the right as much as possible
            while (right_pointer + 1 < n && window_chars.find(s[right_pointer + 1]) == window_chars.end()) {
                window_chars.insert(s[right_pointer + 1]);
                ++right_pointer;
            }

            // Update the maximum length found so far
            max_length = std::max(max_length, right_pointer - left_pointer + 1);
        }
        return max_length;
    }
};
</char>

Optimized Sliding Window with Array (ASCII Mapping)

A more optimized approach leverages the fact that strings are composed of characters, which can be mapped to integer values (like ASCII). Instead of a set, we use a array (acting as a hash map or "bucket") to store the next possible starting position for each character. This alows for direct jumps of the left boundary when a repeat is found, avoiding incremental shifting.

#include <string>
#include <vector>
#include <algorithm>

class SolutionOptimized {
public:
    int lengthOfLongestSubstring(std::string s) {
        // Map character's ASCII value to the index *after* its last occurrence.
        // Initialized to 0, meaning characters haven't been seen yet.
        std::vector<int> char_last_pos(128, 0); 
        int max_length = 0;
        int left_boundary = 0; // Represents the start index of the current valid substring

        for (int right_boundary = 0; right_boundary < s.length(); ++right_boundary) {
            // If the current character's last seen position is beyond or at the current left boundary,
            // it means we've found a repeat within the current window.
            // Update the left boundary to start after the last occurrence of this character.
            left_boundary = std::max(left_boundary, char_last_pos[s[right_boundary]]);
            
            // Update the last seen position for the current character.
            // We store `right_boundary + 1` because the next valid substring must start *after* this character.
            char_last_pos[s[right_boundary]] = right_boundary + 1;
            
            // Calculate the length of the current valid substring and update max_length if it's greater.
            max_length = std::max(max_length, right_boundary - left_boundary + 1);
        }
        return max_length;
    }
};

Intuitive Sliding Window (Tracking Left Boundary)

This variation of the sliding window approach directly tracks the left boundary and uses an unordered\_set to detect repetitions. When a character is encountered that is already in the set, the left boundary is incremented, and the corresponding character is removed from the set, until the repeating character is no longer in the window.

#include <string>
#include <unordered_set>
#include <algorithm>

class SolutionIntuitive {
public:
    int lengthOfLongestSubstring(std::string s) {
        std::unordered_set<char> current_substring_chars;
        int max_length = 0;
        int left_ptr = 0;

        for (int right_ptr = 0; right_ptr < s.length(); ++right_ptr) {
            // If the character at the right pointer is already in our set,
            // we need to shrink the window from the left.
            while (current_substring_chars.count(s[right_ptr])) {
                current_substring_chars.erase(s[left_ptr]);
                ++left_ptr;
            }
            // Add the current character to the set.
            current_substring_chars.insert(s[right_ptr]);
            // Update the maximum length with the current window size.
            max_length = std::max(max_length, right_ptr - left_ptr + 1);
        }
        return max_length;
    }
};