面试题48：最长不含重复字符的子字符串

先还原逐个候选子串查重的蛮力法，再用字符上次出现位置在线维护以当前位置结尾的最长无重复后缀。

学习目标

  • 能用"字符上次出现位置"在线维护以当前位置结尾的最长无重复后缀
  • 能区分子字符串（连续）与子序列（可跳），并解释 DP 与滑动窗口等价
  • 能处理字符集契约（如仅小写字母）与返回实际区间的扩展

从“子字符串必须连续”开始

先预测：输入abcacfrar的答案不是把所有不同字母a、b、c、f、r各挑一个得到5，因为那会跳过中间字符，属于子序列。题目要求的最长不含重复字符的子字符串必须是原串中一段连续区间；其中acfr连续且无重复，长度为4。

扫描到某个位置i时，先不追问全局答案，只问“以i结尾的最长无重复连续后缀有多长”。这个量称为。它能由前一个状态和当前字符的历史位置在线更新。

作者题设还限定字符串只含小写a到z，因此可用长度26的数组记录。数组下标是字符减去a。

图中curLength不是“到目前为止的历史最大值”，而是以当前字符结尾的局部状态；maxLength才是所有结束位置中的最大值。把两者混用，会在后面的重复字符到来时丢掉此前已找到的答案。

作者第一解：蛮力枚举候选子串

作者先展示直接做法。外层固定start，内层让end从start向右延伸，每次用substr复制当前候选，再调用hasDuplication从头检查是否重复。若第一次发现重复，就停止当前start，因为继续向右扩展不可能消除已经存在的重复。

起点逐个扩展并查重该起点最长
0a → ab → abc → abca×abc，长度3
1b → bc → bca → bcac×bca，长度3
2c → ca → cac×ca，长度2
3a → ac → acf → acfr → acfra×acfr，长度4
作者蛮力法为每个起点不断截取子串并从头查重，一旦出现首个重复便停止该起点。
#include <string>
 
bool hasDuplication(
    const std::string& str,
    int position[]) {
    for (int i = 0; i < 26; ++i) {
        position[i] = -1;
    }
 
    for (int i = 0;
         i < static_cast<int>(str.length());
         ++i) {
        const int index = str[i] - 'a';
        if (position[index] >= 0) {
            return true;
        }
        position[index] = index;
    }
    return false;
}
 
int longestSubstringWithoutDuplication_1(
    const std::string& str) {
    int longest = 0;
    int* position = new int[26];
 
    for (int start = 0;
         start < static_cast<int>(str.length());
         ++start) {
        for (int end = start;
             end < static_cast<int>(str.length());
             ++end) {
            const int count = end - start + 1;
            const std::string substring =
                str.substr(start, count);
 
            if (!hasDuplication(
                    substring, position)) {
                if (count > longest) {
                    longest = count;
                }
            } else {
                break;
            }
        }
    }
 
    delete[] position;
    return longest;
}

hasDuplication里的position只被当作“见过或未见过”的标记，所以源码写入字符自己的0到25编号，而不是字符串下标，也能正确判断布尔结果。但这个数组不能据此回答字符在原串哪里出现；动态规划版本会改为保存真实下标。

若把字符集规模也视为可增长，外层起点、内层终点和每次从头查重形成O(n立方)时间，substr还反复分配内存。固定26个小写字母时，无重复候选长度最多26，实际扫描有更紧的常数界；不过这不改变蛮力法重复检查同一片段的本质。

线性状态到底保存什么

处理下标i之前，curLength表示以i减1结尾的当前无重复后缀长度。设当前字符上次出现于prevIndex，距离d等于i减prevIndex。用这个距离与当前长度比较、判断旧字符是否仍在合法区间内，称为。

分三种情况：

  1. 字符从未出现，直接把当前后缀延长1。
  2. 字符出现过，但距离d大于curLength，旧字符已经在当前后缀左侧之外，仍可延长1。
  3. 距离d小于或等于curLength，旧字符就在当前后缀内；新后缀必须从旧字符之后开始，长度改为d。

这里真正的判定是“重复字符是否落在当前窗口内”，不能只看它是否在整段前缀出现过。记录字符上次出现位置，正是为了用一次比较区分窗口内重复和窗口外历史。

curLength 三分支：d = 到上次出现位置的距离分支 1从未出现prev = -1（如 f）curLength + 1不会制造重复分支 2距离 d > curLength旧字符已在后缀外curLength + 1直接增长分支 3距离 d ≤ curLengthc@4，d=2，当前长3curLength = d删旧字符及其左侧best = max(best, curLength)；例 abcacfrar → best = 4（子串 acfr）等号属于“旧字符仍在后缀内”分支：源码条件必须是 d > curLength 才增长，d ≤ curLength 则收缩。用长 26 的 position 数组记录每个字母上次位置；一次遍历 O(n)、O(1)。
等号属于重复仍在当前后缀内的分支，所以源码条件必须是distance大于curLength才增长。

例如扫描abcdaef到第二个a时，旧a位于0，处理前curLength为4，距离也是4。不能把abcda延长成5，因为首尾a重复；应移除旧a，得到bcda，长度仍为4，再由e、f扩展到6。

作者第二解：以结束位置做

源码注释把第二种方法称为动态规划。每个状态只依赖上一个状态与最近出现位置，时间为O(n)，长度26的position数组使额外空间为O(1)。

#include <string>
 
int longestSubstringWithoutDuplication_2(
    const std::string& str) {
    int curLength = 0;
    int maxLength = 0;
 
    int* position = new int[26];
    for (int i = 0; i < 26; ++i) {
        position[i] = -1;
    }
 
    for (int i = 0;
         i < static_cast<int>(str.length());
         ++i) {
        const int prevIndex =
            position[str[i] - 'a'];
 
        if (prevIndex < 0 ||
            i - prevIndex > curLength) {
            ++curLength;
        } else {
            if (curLength > maxLength) {
                maxLength = curLength;
            }
            curLength = i - prevIndex;
        }
 
        position[str[i] - 'a'] = i;
    }
 
    if (curLength > maxLength) {
        maxLength = curLength;
    }
 
    delete[] position;
    return maxLength;
}

作者只在发生窗口内重复时把旧curLength写入maxLength，并在循环结束后补一次比较。这是正确的，因为没有重置时curLength只会增长；也可以每轮更新后统一执行maxLength取较大值，逻辑更直接。

以abcacfrar为例，curLength依次为1、2、3、3、2、3、4、4、2，maxLength最终为4。扫描第二个c时，它上次在2，距离2不大于此前长度3，因此新后缀只能是索引3到4的ac，长度2。

其实是同一状态

若用窗口写法，令left为当前无重复区间左端，right为扫描位置。只有当当前字符上次位置不小于left时，才把left跳到旧位置加1。窗口长度是right减left加1。

动态版在处理right前有curLength，因此旧窗口左端等于right减curLength。条件“prevIndex小于旧left”等价于“right减prevIndex大于curLength”。两种表述只是保存变量不同：

动态规划：
    curLength = 以right结尾的无重复后缀长度
 
滑动窗口：
    left = 该后缀的左边界
 
互相换算：
    left = right - curLength + 1
    curLength = right - left + 1

所以原书单元中的“动态规划或滑动窗口”不是两道互不相关的算法。它们共享同一个不变量：处理完成后，保存的区间以当前位置结尾、内部无重复，并且在所有以当前位置结尾的合法区间中最长。

窗口左端永不左移。若某字符旧位置已在窗口外，使用last加1直接赋值会让left倒退；必须先判断last是否不小于left，或写成left等于left与last加1的较大值。旧页虽然给出窗口代码，但没有还原作者curLength距离判定，也没有解释两者的等价关系。

正确性：为什么只看最近一次出现

假设当前字符c此前出现过多次。若最近一次c已在当前后缀之外，更早的c一定更靠左，也都在外；可以安全延长。若最近一次c在当前后缀内，为消除重复，左端至少要越过它；越过最近一次后，所有更早的c也自然被排除。

因此只保存最近位置既充分又必要，无需字符的完整位置列表。重置后的区间从prevIndex加1到i，内部原有字符原本就互不重复，删除前缀不会制造重复，再加入的新c与旧c已分离，所以新区间合法。

它还是最长的：任何以i结尾且无重复的区间都不能包含prevIndex处的c，左端至少是prevIndex加1；选择这个最早合法左端得到最大长度i减prevIndex。若旧c在窗口外，沿用旧左端并加入c已经是最长。

全局答案取所有结束位置的当前无重复后缀最大值。任意连续子字符串都有唯一结束位置，因此不会漏掉最优区间。

字符集契约不能被256数组掩盖

作者严格假设输入只含a到z。输入允许哪些字符、以及字符如何映射到状态数组下标，构成。表达式str[i]减a在此条件下得到0到25；大写、标点或UTF-8中文会产生负下标或超过25，导致越界访问和未定义行为。

维度作者契约直接后果扩展策略
字符范围仅a到zposition[ch - 'a']下标0到25
大写A不在题设内产生负下标先校验或改用映射
ASCII标点不在题设内可能越界拒绝或扩展表
UTF-8中文多字节编码按字节不等于按字符先解码Unicode码点
空字符串合法边界循环零次返回0
返回内容作者只返回长度不保存最佳起点扩展时同步记录区间
长度26的数组是题设优化，不是可直接处理任意文本的通用字符表。

即使只处理单字节，也要把char转换成unsigned char后再作数组下标，因为某些平台char有符号。若输入字符集未知，使用unordered_map保存最近位置能避免固定表越界，但不会自动解决UTF-8码点边界。

返回实际区间的工程扩展

作者只返回长度。若产品还要显示子字符串，更新历史最大值时同步保存bestStart即可。下面版本面向任意字节串，并明确返回字节区间；它不声称按Unicode字符计数。

#include <array>
#include <string_view>
#include <utility>
 
std::pair<std::size_t, std::size_t>
longestUniqueByteRange(std::string_view text) {
    std::array<std::size_t, 256> last;
    last.fill(std::string_view::npos);
 
    std::size_t left = 0;
    std::size_t bestStart = 0;
    std::size_t bestLength = 0;
 
    for (std::size_t right = 0;
         right < text.size();
         ++right) {
        const auto byte =
            static_cast<unsigned char>(text[right]);
        if (last[byte] != std::string_view::npos &&
            last[byte] >= left) {
            left = last[byte] + 1;
        }
        last[byte] = right;
 
        const std::size_t length =
            right - left + 1;
        if (length > bestLength) {
            bestStart = left;
            bestLength = length;
        }
    }
    return {bestStart, bestLength};
}

并列最长区间时，这段代码保留最早出现者，因为只在严格更长时更新。若需求是保留最后一个、返回全部并列区间或按字典序选择，必须在相等分支中定义规则。

空字符串循环不执行，返回起点0、长度0；单字符返回0、1。对超大输入使用size_t避免把length强制缩为int，但若对外协议只接受32位长度，转换前仍要检查范围。

作者10组测试的覆盖意图

作者main实际调用test1到test10，每组都让蛮力法和动态规划法与同一个expected比较：

  1. abcacfrar期望4，最优段在中后部。
  2. acfrarabc期望4，最优段可出现在前部和尾部。
  3. arabcacfr期望4，重复分布错位。
  4. aaaa期望1，连续相同字符每次重置为1。
  5. abcdefg期望7，整串无重复，循环结束才刷新最大值。
  6. aaabbbccc期望2，跨字符分段可形成ab或bc。
  7. abcdcba期望4，中心向两侧重复。
  8. abcdaef期望6，覆盖距离等于当前长度的边界。
  9. a期望1，最小非空输入。
  10. 空字符串期望0，两版循环都不进入。

源码的test函数只打印passed或FAILED，不用断言中止；自动化环境应让失败产生非零退出码。作者未覆盖非法大写、标点、UTF-8、超长输入、返回实际区间或并列选择规则，因为这些都不在原题公开契约中。

#include <cassert>
 
void testLongestSubstring() {
    assert(longestSubstringWithoutDuplication_2(
        "abcacfrar") == 4);
    assert(longestSubstringWithoutDuplication_2(
        "acfrarabc") == 4);
    assert(longestSubstringWithoutDuplication_2(
        "arabcacfr") == 4);
    assert(longestSubstringWithoutDuplication_2(
        "aaaa") == 1);
    assert(longestSubstringWithoutDuplication_2(
        "abcdefg") == 7);
    assert(longestSubstringWithoutDuplication_2(
        "aaabbbccc") == 2);
    assert(longestSubstringWithoutDuplication_2(
        "abcdcba") == 4);
    assert(longestSubstringWithoutDuplication_2(
        "abcdaef") == 6);
    assert(longestSubstringWithoutDuplication_2(
        "a") == 1);
    assert(longestSubstringWithoutDuplication_2(
        "") == 0);
}

随机小写字符串可让两版作者算法对拍。蛮力法适合作为可信参考，但测试生成长度应受控；若两版都复用同一个最近位置辅助函数，就会降低发现共享错误的能力。

复杂度与方案选择

作者动态版对每个字符做常数次读取和写入，时间O(n)；position固定26项，额外空间O(1)。若字符集规模记为k，初始化和存储可写成O(k)，总时间O(n加k)。

滑动窗口配set也能做到O(n)：遇重复时逐个移除左端字符，左右指针都最多走n步。但最近位置表可一次跳过整段，更直接表达作者的距离状态。不能因为set版本有内层while就误判为O(n平方)，摊还分析要统计每个字符最多进入和离开一次。

需要列出所有无重复子串时，输出规模本身可能是O(n平方)，线性算法只能给最长值或有限个代表区间。需要在线处理字符流时，最近位置与left可持续维护；若只保留窗口内容而不保留全部历史，仍能输出当前最长长度，但要保存历史最佳文本则需额外拷贝。

本章练习

练习

问题 1： 子字符串与子序列的区别是什么？为什么本题要求子字符串？

问题 2： DP 状态"以 i 结尾的最长无重复后缀"如何在线更新？

问题 3： DP 与滑动窗口为什么等价？

本章回顾

  1. 最长不含重复字符的子字符串必须连续，不能跳选字符。
  2. 作者先用蛮力法枚举起点和终点，并对每个候选从头查重。
  3. 线性法的curLength是以当前位置结尾的最长无重复后缀长度。
  4. 字符上次出现位置只有落在当前后缀内时才迫使状态重置。
  5. 距离大于curLength才可增长；距离等于时旧字符仍在窗口内。
  6. 动态规划或滑动窗口是同一状态的长度表示与左边界表示。
  7. 作者的26槽数组依赖仅含a到z，不能直接处理任意字节或Unicode。
  8. 10组测试全部由main执行，abcdaef专门覆盖等号边界。

名词解释

名词解释

本章出现的专业名词，用大白话再讲一遍。

最长无重复后缀
以当前位置结尾、不含重复字符的最长连续子串长度。
动态规划
用前一状态与历史位置递推当前状态，O(n) 求解。
滑动窗口
用左右指针维护无重复窗口，与 DP 状态等价。
复习本章（5 题）

讨论

评论区加载中…