leetcode 上有一道叫做 最长的美好子字符串 的题，挺有趣。
题目描述如下：
对于一个字符串的任一字符，它的大小写形式都在这个字符串之中，则称这个字符串是美好字符串。 给定一个字符串，返回它的最长的美好子字符串，如果有多个，则返回靠左的那个。
比如说，字符串 YazaAay 的最长美好子串是 aAa 。
虽然难度标的是「简单题」，实际做起来并不简单。
本文分享我对于这个题目的一个解法。
思路分析 ¶
我们可以把大小写字母的关系称为互为 镜像 的，比如说字母 A 和 a 互为镜像。
镜像字符的转换函数 mirror
char mirror(char ch) {
if (isupper(ch)) return tolower(ch);
return toupper(ch);
}
现在考虑一个字符串例子 cBCbdABDCc ，它的最长美好字符串应该是 cBCb。
分析过程是这样的：
首先，注意到字母
A的镜像字母a在整个字符串中不存在。我们称其为一个 断点 :
cBCbdABDCc在断点
A的左侧cBCbd中继续寻找美好字符串。可以进一步发现断点
d，因为它的镜像字母D不在当前考察的范围内：cBCbd。此时可以看到，再左边的
cBCb是一个美好字符串，其长度是4。在断点
A的右侧BDCc中继续寻找美好字符串。类似的，可以找到两个新的断点：
BDCc。 并发现一个长度为2的美好字符串Cc。
其实就是 分治递归 的过程。
断点会把当前考察的区间分割成多个小区间，然后我们进一步考察各个小区间。直到找不到任何断点为止即可。
算法过程 ¶
我们的算法主过程可以描述为：
- 考察当前左闭右开的区间
[L, R), 寻找所有的断点位置i。 - 将断点
i当做新的右界，递归考察子区间[L, i)。 - 考察完毕后，跨过当前子区间，左界前进到
i+1处，继续寻找断点。 - 汇总被断点分割的小区间上的结果，取最长者返回。
- 如果找不到断点，则返回整个当前区间，作为一个美好子串的区间结果。
用伪代码来描述主过程：
def dfs(L, R):
for i in [L, R):
if i is a breakpoint:
left, right = dfs(L, i) if longer
L = i + 1
return [left, right)
断点检查和预处理 ¶
接下来的问题是，如何检查一个字符在当前区间内是否是断点呢？
断点的含义是说，其镜像字符在当前区间内未出现。
如果当前字符最近的镜像字符都不在界内，那么它就是一个断点。
我们可以把一个字符的附近的镜像字符信息预处理下来。
预处理两个数组：
pre数组：pre[i]表示字符s[i]的镜像字符在其左边最近出现的位置。post数组：post[i]表示字符s[i]的镜像字符在其右边最近出现的位置。
这两个数组如何生成，非常简单，只需要借助哈希表即可，不再展开讨论。
预处理生成 pre 数组 - C++
// pre 记录上一次其镜像字符出现的位置. 默认是 -1;
vector<int> make_pre(string& s) {
// m 记录一个字符最近出现的位置
unordered_map<char, int> m;
vector<int> pre(s.size(), -1);
for (int i = 0; i < s.size(); i++) {
// 当前位置，一个字符在左边出现的最新位置
m[s[i]] = i;
// 镜像字符
auto mch = mirror(s[i]);
if (m.find(mch) != m.end()) pre[i] = m[mch];
return pre;
}
}
预处理生成 post 数组 - C++
// post 记录上一次其镜像字符出现的位置. 默认是 N
vector<int> make_post(string& s) {
// m 记录一个字符最近出现的位置 (从右向左扫)
unordered_map<char, int> m;
vector<int> post(s.size(), s.size());
for (int i = s.size() - 1; i >= 0; --i) {
// 当前位置，一个字符在左边出现的最新位置
m[s[i]] = i;
auto mch = mirror(s[i]); // 镜像字符
if (m.find(mch) != m.end()) post[i] = m[mch];
}
return post;
}
判断一个字符是否为一个断点，只需判断其 pre 和 post 的镜像字符是否在界内，伪代码如下：
def is_breakpoint(i):
return pre[i] < L and post[i] >= R
总的算法实现 ¶
总的主过程就清晰了：先预处理，然后 dfs 搜索断点汇总结果，伪代码如下：
def longestNiceSubstring(s):
pre = make_pre(s)
post = make_post(s)
[left, right) = dfs(s, L=0, R=N, pre, post)
return s.substr(left, right)
最终的 C++ 代码实现见 leetcode-1763-longest-nice-substring 。
复杂度分析 ¶
最好情形，没有任何断点的情况，比如 aAbBcCdD ，一趟就可以跑完，时间复杂度是 O(N) 。
对于有断点，但是断点的位置没有形成递归向下条件的，也是 O(N) 的。比如说 abcdefg，虽然所有的字符都是断点， 但是其递归深度为 0， 所有断点在第一次扫描过程中就可以检测到，整个过程就是在从左到右扫描断点。
对于最差情形，需要递归地尽可能深，因为每次递归都会发生回溯，回到左边界。
递归尽可能深的情况，发生在断点的发现总是延迟的情形。一个断点的发现，会进一步导致已经扫描过的正常字符变成新的断点。
比如下面的情况，b 和 B 在上一层的区间内，不是断点，但是当 A 确认成为断点后，再递归两边区间的时候，b 和 B 才被检测成为新的断点。
最坏的情况的一个例子 dcDbdCDAdcDBdCD ，这个字符串的最长美好子串的长度仅为 0 。 因为它的每个字符都是断点，而且每个断点总是延迟发现的。
这个最差情形的时间复杂度和快排是一样的，递归深度 log(N) ， 时间复杂度是 Nlog(N) 。
（完）
