T4-1.md

第4关：最长无重复字符串的长度

题目链接

题目大意

输入非空字符串，求最长无重复字母的连续子串的长度

数据范围

字符串长度 $n<100$，字符集为小写字母（大小 $m<=26$ ）

算法思路

朴素思路

题目要求字串连续，故二层循环枚举字串首尾，内部再套一层循环, 采用一个vis数组记录已出现的字符来判断是否无重复字符

时间复杂度：$O(n^3)$

改良1

注意到枚举字符串开头与判断是否存在重复字符直接相关（有重复字符才迫使字符串开头不可进一步向前延申），于是仅需枚举字符串末尾，内部从当前的字符串末尾开始向前循环寻找最长无重复字串

时间复杂度：$O(n^2)$

改良2

对字符串末尾应用相似的判重逻辑，使用如蠕动指针 / 滑动窗口的思想，使用两个指针/下标来标记当前搜索区间首尾，尾指针不断尝试向后移动，将遇见的字符加入vis数组，直到出现重复字符，开始向前移动首指针，将首指针对应的元素移除出vis数组，直至不存在重复字符。每次移动尾指针的同时更新当前最大长度，尾指针移动到输入字符串末尾终止。

时间复杂度：$O(n)$

样例代码

#include <cstring> // for strlen
#include <iostream>
using namespace std;

const int maxn = 100 + 5; // 字符串长度上限 + 余量

bool vis[256]; // 字符集大小256

int main() {
	char s[maxn];
	cin.getline(s, maxn);
	int n = strlen(s), ans = 0;
	for(int i = 0, j = 0; j < n; j++) {
		while(vis[s[j]]) { // 当前区间 [i, j) 中存在与第j个字符相同的字符
			vis[s[i]] = false; // 从左端点开始逐个删除字符
			++i;
		}
		vis[s[j]] = true;
		ans = max(ans, j - i + 1); // 更新最大区间长度
	}
	cout << ans << endl;
	return 0;
}

小练习

如何证明改良2的时间复杂度是$O(n)$

如果字符集大小$m$很大（e.g. ${10}^{18}$ 量级），内存无法支持开如此大的vis数组，如何使用较小的内存，尽可能快的完成查重工作呢？