无重复字符最长子串计算C++代码超时问题优化咨询

待实现功能为计算给定字符串中无重复字符的最长子串长度，需满足以下测试规则：

• 输入a23a8901时返回7，对应合法子串为23a8901
• 输入a23a89a1时返回5，对应合法子串为23a89

现有代码在短字符串输入下运行结果正确，但输入超长字符串时会触发时间超限，代码如下：

int lengthOfLongestSubstring(string s) {   
    int outerMax = 1;
    for(int i = 0; i < s.length() - 1; i++) {
        int currentMax = 1;
        cout << "I: " << i << "\n";
        for(int j = i + 1; j < s.length() ; j++) {
            int counterInnerMax = 1;
            int noBreak = 0;
            for(int k = j ; k>i ; k--) {
                int l = k;
                while( l>i && s[k] != s[l-1] ) {
                    cout << "value of K: " << k << " then " <<  "value of l: " << l << "\n";
                    l--;
                }
            
                if(l == i) {
                    cout << "enter here at value l being: " << l << " !\n";
                    counterInnerMax++;
                    currentMax = counterInnerMax;
                    cout << "CurrentMax value: " << currentMax << "\n";
                } else {
                    noBreak = 1;
                    break;
                }
              
            }
            if(noBreak) {
                break;
            }
        }
        outerMax = max(outerMax,currentMax);
    }
    return outerMax;
}

• 时间复杂度爆炸：现有代码嵌套了三层for循环加一层while循环，最坏时间复杂度到了*O(n⁴)*级别，字符串长度到1e3级别就会明显卡顿，更长的字符串直接超时是必然结果。
• 重复计算完全没有规避：每次固定左起点i向右扩展j的时候，判断s[j]是否和前面的字符重复，都要从j位置倒回去逐字符比一遍，之前已经确认过的无重复区间信息完全没复用，做了海量无效比对。
• 调试打印拖慢速度：代码里留了大量cout打印语句，IO操作的耗时比内存计算高几个数量级，长字符串下这些打印会占用绝大多数运行时间。
• 边界case处理缺失：输入空字符串的时候，代码初始值直接设为1返回，结果错误。

直接用滑动窗口+位置标记数组的思路，把时间复杂度压到O(n)，整个字符串只需要遍历一次：

• 维护左右边界标记left和right，两个边界围起来的区间就是当前找到的以right为终点的最长无重复子串
• 开一个长度128的数组（覆盖全部ASCII字符），存每个字符上一次出现的索引位置，初始值统一设为-1
• 右边界right从0开始逐位向右遍历：如果当前字符上次出现的位置在left的右边，说明当前窗口里有重复，直接把left跳到重复字符上次出现位置的下一位，跳过重复区间
• 每一步更新当前字符的最新出现位置，计算当前窗口的长度，和全局最大值比较更新即可
• 提交前把所有调试用的cout语句全部删掉，不要留多余的IO操作

int lengthOfLongestSubstring(string s) {
    int strLen = s.size();
    if (strLen == 0) return 0;
    vector<int> lastOccur(128, -1);
    int maxSubLen = 0;
    int left = 0;
    for (int right = 0; right < strLen; right++) {
        if (lastOccur[s[right]] >= left) {
            left = lastOccur[s[right]] + 1;
        }
        lastOccur[s[right]] = right;
        maxSubLen = max(maxSubLen, right - left + 1);
    }
    return maxSubLen;
}

内容的提问来源于stack exchange，提问作者hodondo