Given a string s, determine the length of the longest substring that contains no repeating characters.

Example 1:

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

Example 2:

Input: s = "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.

Example 3:

Input: s = "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3. Note that the answer must be a substring; "pwke" is a subsequence and not a substring.

Constraints:

• 0 <= s.length <= 5 * 10^4
• s consists of English letters, digits, symbols, and spaces.

Approach

Since the input string comrpises standard printable characters, their ASCII values remain within a fixed range. This problem can be efficiently solved using a sliding window technique combined with a data structure to track character occurrences.

We maintain two pointers to define the boundaries of our current window: start and end. As we iterate through the string, we expand the window by moving the end pointer. If we encounter a character that already exists within the current window, we adjust the start pointer to exclude the previous occurrence, enusring all characters inside the window remain unique. Throughout this process, we continuously calculate and store the maximum window length observed.

Implementation

The following solution utilizes a hash map to record the most recent index of each character. This allows us to instantly jump the start pointer forward when a duplicate is detected, achieving optimal linear time complexity.

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

int computeLongestUniqueSubstr(std::string inputText) {
    std::unordered_map<char, int> lastPositionMap;
    int longestLen = 0;
    int windowStart = 0;

    for (int windowEnd = 0; windowEnd < inputText.size(); ++windowEnd) {
        char currentChar = inputText[windowEnd];
        
        // If the character was seen and is inside the current window, move start
        if (lastPositionMap.find(currentChar) != lastPositionMap.end()) {
            windowStart = std::max(windowStart, lastPositionMap[currentChar] + 1);
        }
        
        lastPositionMap[currentChar] = windowEnd;
        longestLen = std::max(longestLen, windowEnd - windowStart + 1);
    }
    
    return longestLen;
}