把 $s$ 按照连续相同字母分成若干段，每段保留至多 $2$ 个字母。

示例 2 的 $s=\texttt{aaabaaaa}$，分成三段 $\texttt{aaa} + \texttt{b} + \texttt{aaaa}$，其中第一段和第三段不符合要求（有三个连续相同字符），保留 $2$ 个字母，变成 $\texttt{aa} + \texttt{b} + \texttt{aa} = \texttt{aabaa}$。

用一个计数器 $\textit{cnt}$ 统计每一段的当前长度，如果 $\textit{cnt}<3$ 就把当前字母加入答案。

如果当前字母和下一个字母不同，则重置 $\textit{cnt}=0$，统计下一段的长度。

###py

class Solution:
    def makeFancyString(self, s: str) -> str:
        ans = []
        cnt = 0
        for i, ch in enumerate(s):
            cnt += 1
            if cnt < 3:
                ans.append(ch)
            if i < len(s) - 1 and ch != s[i + 1]:
                cnt = 0  # 当前字母和下个字母不同，重置计数器
        return ''.join(ans)

###py

class Solution:
    def makeFancyString(self, s: str) -> str:
        ans = []
        for _, group in groupby(s):
            ans += list(group)[:2]
        return ''.join(ans)

###java

class Solution {
    public String makeFancyString(String s) {
        StringBuilder ans = new StringBuilder();
        int cnt = 0;
        for (int i = 0; i < s.length(); i++) {
            cnt++;
            if (cnt < 3) {
                ans.append(s.charAt(i));
            }
            if (i < s.length() - 1 && s.charAt(i) != s.charAt(i + 1)) {
                cnt = 0; // 当前字母和下个字母不同，重置计数器
            }
        }
        return ans.toString();
    }
}

###cpp

class Solution {
public:
    string makeFancyString(string s) {
        string ans;
        int cnt = 0;
        for (int i = 0; i < s.size(); i++) {
            cnt++;
            if (cnt < 3) {
                ans += s[i];
            }
            if (i < s.size() - 1 && s[i] != s[i + 1]) {
                cnt = 0; // 当前字母和下个字母不同，重置计数器
            }
        }
        return ans;
    }
};

###c

char* makeFancyString(char* s) {
    int cnt = 0, j = 0;
    for (int i = 0; s[i]; i++) {
        cnt++;
        if (cnt < 3) {
            s[j++] = s[i];
        }
        if (s[i] != s[i + 1]) {
            cnt = 0; // 当前字母和下个字母不同，重置计数器
        }
    }
    s[j] = '\0';
    return s;
}

###go

func makeFancyString(s string) string {
ans := []byte{}
cnt := 0
for i, ch := range s {
cnt++
if cnt < 3 {
ans = append(ans, byte(ch))
}
if i < len(s)-1 && byte(ch) != s[i+1] {
cnt = 0 // 当前字母和下个字母不同，重置计数器
}
}
return string(ans)
}

###js

var makeFancyString = function(s) {
    const ans = [];
    let cnt = 0;
    for (let i = 0; i < s.length; i++) {
        cnt++;
        if (cnt < 3) {
            ans.push(s[i]);
        }
        if (i < s.length - 1 && s[i] !== s[i + 1]) {
            cnt = 0; // 当前字母和下个字母不同，重置计数器
        }
    }
    return ans.join('');
};

###rust

impl Solution {
    pub fn make_fancy_string(s: String) -> String {
        let s = s.into_bytes();
        let mut ans = vec![];
        let mut cnt = 0;
        for (i, &ch) in s.iter().enumerate() {
            cnt += 1;
            if cnt < 3 {
                ans.push(ch);
            }
            if i + 1 < s.len() && ch != s[i + 1] {
                cnt = 0; // 当前字母和下个字母不同，重置计数器
            }
        }
        unsafe { String::from_utf8_unchecked(ans) }
    }
}

复杂度分析

• 时间复杂度：$\mathcal{O}(n)$，其中 $n$ 是 $s$ 的长度。
• 空间复杂度：$\mathcal{O}(n)$ 或 $\mathcal{O}(1)$，取决于实现。

分类题单

如何科学刷题？

1. 滑动窗口与双指针（定长/不定长/单序列/双序列/三指针/分组循环）
2. 二分算法（二分答案/最小化最大值/最大化最小值/第K小）
3. 单调栈（基础/矩形面积/贡献法/最小字典序）
4. 网格图（DFS/BFS/综合应用）
5. 位运算（基础/性质/拆位/试填/恒等式/思维）
6. 图论算法（DFS/BFS/拓扑排序/基环树/最短路/最小生成树/网络流）
7. 动态规划（入门/背包/划分/状态机/区间/状压/数位/数据结构优化/树形/博弈/概率期望）
8. 常用数据结构（前缀和/差分/栈/队列/堆/字典树/并查集/树状数组/线段树）
9. 数学算法（数论/组合/概率期望/博弈/计算几何/随机算法）
10. 贪心与思维（基本贪心策略/反悔/区间/字典序/数学/思维/脑筋急转弯/构造）
11. 链表、二叉树与回溯（前后指针/快慢指针/DFS/BFS/直径/LCA/一般树）
12. 字符串（KMP/Z函数/Manacher/字符串哈希/AC自动机/后缀数组/子序列自动机）

我的题解精选（已分类）

欢迎关注 B站@灵茶山艾府

核心思路：把相同的子树映射为相同的字符串，就能用哈希表去重了。

如何把子树转化成字符串？为了准确判断两棵子树的结构是否相同，需要做到两点：

1. 字符串需要包含子树所有节点的文件夹名。
2. 字符串要能够表达节点的父子关系。

考察树的递归过程，把向下「递」的动作用一个非字母字符表示，向上「归」的动作用另一个非字母字符表示，就可以描述一棵树的形状了（用非字母字符是为了与文件夹名区分开）。比如说，用左括号表示递，用右括号表示归。从节点 $\texttt{x}$ 向下递到节点 $\texttt{y}$，再归回 $\texttt{x}$，就可以表示为 $\texttt{x(y)}$。如果 $\texttt{x}$ 有两个儿子 $\texttt{y}$ 和 $\texttt{z}$（并且这两个儿子都是叶子），那么子树 $\texttt{x}$ 就可以表示为 $\texttt{x(y)(z)}$。

一般地，定义如下括号表达式：

• 对于叶子节点，设其文件夹名为 $S$，则其括号表达式就是 $S$。
• 对于任意子树 $x$，设 $x$ 的儿子为 $y_1,y_2,\ldots,y_k$，则子树 $x$ 的括号表达式为
  $$
  x 的文件夹名 + (子树 y_1 的表达式) + (子树 y_2 的表达式) + \cdots + (子树 y_k 的表达式)
  $$

{:width=300}

看示例 4，子树 $\texttt{x}$ 的括号表达式为 $\texttt{x(y)}$，子树 $\texttt{a}$ 的括号表达式为 $\texttt{a(x(y))(z)}$，子树 $\texttt{b}$ 的括号表达式为 $\texttt{b(x(y))(z)}$。

根据题意，我们不关心子树根节点的文件夹名，在去掉子树根节点后，子树 $\texttt{a}$ 和子树 $\texttt{b}$ 的括号表达式都是 $\texttt{(x(y))(z)}$，所以这两个文件夹「包含非空且相同的子文件夹集合，并具有相同的子文件夹结构」。

括号表达式既包含了文件夹名，又通过括号的嵌套关系表达了父子关系，因此可用于判断两个文件夹是否为相同文件夹。

你可能会问：如果子树 $\texttt{b}$ 的两棵子树是 $\texttt{z}$ 在左，$\texttt{x(y)}$ 在右呢？得到的表达式为 $\texttt{(z)(x(y))}$，这样没法判断两棵子树相同呀？

解决办法：在构造括号表达式时，先把子树 $y_1,y_2,\ldots,y_k$ 的表达式按照字典序排序，再把表达式依次拼接，就可以避免出现上述情况了。

代码实现时，用 字典树 表示这个文件系统，节点保存文件夹名称。注意这与一般的字典树不同，不是二十六叉树那种用单个字母对应节点，而是用一整个字符串（文件夹名）对应节点。这棵字典树一个节点（文件夹）最多能有 $20000$ 个儿子（子文件夹）。

用 $\textit{paths}$ 构建完字典树后，DFS 这棵树，按照前文的规则生成括号表达式 $\textit{subTreeExpr}$：

• 如果首次遇到 $\textit{subTreeExpr}$，那么把 $\textit{subTreeExpr}$ 及其对应的子树根节点保存到哈希表中。
• 否则我们找到了重复的文件夹，把哈希表中 $\textit{subTreeExpr}$ 对应的节点，以及当前节点，都标记为待删除。

最后，再次 DFS（回溯）这棵字典树，仅访问未被删除的节点，同时用一个列表 $\textit{path}$ 记录路径上的文件夹名。每次递归到一个节点，就把 $\textit{path}$ 的一个拷贝加到答案中。做法类似 257. 二叉树的所有路径。

class TrieNode:
    __slots__ = 'son', 'name', 'deleted'

    def __init__(self):
        self.son = {}
        self.name = ''  # 文件夹名称
        self.deleted = False  # 删除标记


class Solution:
    def deleteDuplicateFolder(self, paths: List[List[str]]) -> List[List[str]]:
        root = TrieNode()
        for path in paths:
            # 把 path 插到字典树中，见 208. 实现 Trie
            cur = root
            for s in path:
                if s not in cur.son:
                    cur.son[s] = TrieNode()
                cur = cur.son[s]
                cur.name = s

        expr_to_node = {}  # 子树括号表达式 -> 子树根节点

        def gen_expr(node: TrieNode) -> str:
            if not node.son:  # 叶子
                return node.name  # 表达式就是文件夹名

            # 每个子树的表达式外面套一层括号
            expr = sorted('(' + gen_expr(son) + ')' for son in node.son.values())
            sub_tree_expr = ''.join(expr)  # 按字典序拼接所有子树的表达式
            if sub_tree_expr in expr_to_node:  # 哈希表中有 sub_tree_expr，说明有重复的文件夹
                expr_to_node[sub_tree_expr].deleted = True  # 哈希表中记录的节点标记为删除
                node.deleted = True  # 当前节点标记为删除
            else:
                expr_to_node[sub_tree_expr] = node

            return node.name + sub_tree_expr

        for son in root.son.values():
            gen_expr(son)

        ans = []
        path = []

        # 在字典树上回溯，仅访问未被删除的节点，并将路径记录到答案中
        # 类似 257. 二叉树的所有路径
        def dfs(node: TrieNode) -> None:
            if node.deleted:
                return
            path.append(node.name)
            ans.append(path.copy())  # path[:]
            for child in node.son.values():
                dfs(child)
            path.pop()  # 恢复现场

        for son in root.son.values():
            dfs(son)

        return ans

class Solution {
    private static class TrieNode {
        Map<String, TrieNode> son = new HashMap<>();
        String name; // 文件夹名称
        boolean deleted = false; // 删除标记
    }

    public List<List<String>> deleteDuplicateFolder(List<List<String>> paths) {
        TrieNode root = new TrieNode();
        for (List<String> path : paths) {
            // 把 path 插到字典树中，见 208. 实现 Trie
            TrieNode cur = root;
            for (String s : path) {
                if (!cur.son.containsKey(s)) {
                    cur.son.put(s, new TrieNode());
                }
                cur = cur.son.get(s);
                cur.name = s;
            }
        }

        Map<String, TrieNode> exprToNode = new HashMap<>(); // 子树括号表达式 -> 子树根节点
        for (TrieNode son : root.son.values()) {
            genExpr(son, exprToNode);
        }

        List<List<String>> ans = new ArrayList<>();
        List<String> path = new ArrayList<>();
        for (TrieNode son : root.son.values()) {
            dfs(son, path, ans);
        }
        return ans;
    }

    private String genExpr(TrieNode node, Map<String, TrieNode> exprToNode) {
        if (node.son.isEmpty()) { // 叶子
            return node.name; // 表达式就是文件夹名
        }

        List<String> expr = new ArrayList<>();
        for (TrieNode son : node.son.values()) {
            // 每个子树的表达式外面套一层括号
            expr.add("(" + genExpr(son, exprToNode) + ")");
        }
        Collections.sort(expr);

        String subTreeExpr = String.join("", expr); // 按字典序拼接所有子树的表达式
        TrieNode n = exprToNode.get(subTreeExpr);
        if (n != null) { // 哈希表中有 subTreeExpr，说明有重复的文件夹
            n.deleted = true; // 哈希表中记录的节点标记为删除
            node.deleted = true; // 当前节点标记为删除
        } else {
            exprToNode.put(subTreeExpr, node);
        }

        return node.name + subTreeExpr;
    }

    // 在字典树上回溯，仅访问未被删除的节点，并将路径记录到答案中
    // 类似 257. 二叉树的所有路径
    private void dfs(TrieNode node, List<String> path, List<List<String>> ans) {
        if (node.deleted) {
            return;
        }
        path.add(node.name);
        ans.add(new ArrayList<>(path)); // 记录路径
        for (TrieNode son : node.son.values()) {
            dfs(son, path, ans);
        }
        path.removeLast(); // 恢复现场
    }
}

struct TrieNode {
    unordered_map<string, TrieNode*> son;
    string name; // 文件夹名称
    bool deleted = false; // 删除标记
};

class Solution {
public:
    vector<vector<string>> deleteDuplicateFolder(vector<vector<string>>& paths) {
        TrieNode* root = new TrieNode();
        for (auto& path : paths) {
            // 把 path 插到字典树中，见 208. 实现 Trie
            TrieNode* cur = root;
            for (auto& s : path) {
                if (!cur->son.contains(s)) {
                    cur->son[s] = new TrieNode();
                }
                cur = cur->son[s];
                cur->name = s;
            }
        }

        unordered_map<string, TrieNode*> expr_to_node; // 子树括号表达式 -> 子树根节点

        auto gen_expr = [&](this auto&& gen_expr, TrieNode* node) -> string {
            if (node->son.empty()) { // 叶子
                return node->name; // 表达式就是文件夹名
            }

            vector<string> expr;
            for (auto& [_, son] : node->son) {
                // 每个子树的表达式外面套一层括号
                expr.emplace_back("(" + gen_expr(son) + ")");
            }
            ranges::sort(expr);

            string sub_tree_expr;
            for (auto& e : expr) {
                sub_tree_expr += e; // 按字典序拼接所有子树的表达式
            }

            if (expr_to_node.contains(sub_tree_expr)) { // 哈希表中有 sub_tree_expr，说明有重复的文件夹
                expr_to_node[sub_tree_expr]->deleted = true; // 哈希表中记录的节点标记为删除
                node->deleted = true; // 当前节点标记为删除
            } else {
                expr_to_node[sub_tree_expr] = node;
            }

            return node->name + sub_tree_expr;
        };

        for (auto& [_, son] : root->son) {
            gen_expr(son);
        }

        vector<vector<string>> ans;
        vector<string> path;

        // 在字典树上回溯，仅访问未被删除的节点，并将路径记录到答案中
        // 类似 257. 二叉树的所有路径
        auto dfs = [&](this auto&& dfs, TrieNode* node) -> void {
            if (node->deleted) {
                return;
            }
            path.push_back(node->name);
            ans.push_back(path);
            for (auto& [_, son] : node->son) {
                dfs(son);
            }
            path.pop_back(); // 恢复现场
        };

        for (auto& [_, son] : root->son) {
            dfs(son);
        }

        return ans;
    }
};

type trieNode struct {
son     map[string]*trieNode
name    string // 文件夹名称
deleted bool   // 删除标记
}

func deleteDuplicateFolder(paths [][]string) (ans [][]string) {
root := &trieNode{}
for _, path := range paths {
// 把 path 插到字典树中，见 208. 实现 Trie
cur := root
for _, s := range path {
if cur.son == nil {
cur.son = map[string]*trieNode{}
}
if cur.son[s] == nil {
cur.son[s] = &trieNode{}
}
cur = cur.son[s]
cur.name = s
}
}

exprToNode := map[string]*trieNode{} // 子树括号表达式 -> 子树根节点
var genExpr func(*trieNode) string
genExpr = func(node *trieNode) string {
if node.son == nil { // 叶子
return node.name // 表达式就是文件夹名
}

expr := make([]string, 0, len(node.son)) // 预分配空间
for _, son := range node.son {
// 每个子树的表达式外面套一层括号
expr = append(expr, "("+genExpr(son)+")")
}
slices.Sort(expr)

subTreeExpr := strings.Join(expr, "") // 按字典序拼接所有子树的表达式
n := exprToNode[subTreeExpr]
if n != nil { // 哈希表中有 subTreeExpr，说明有重复的文件夹
n.deleted = true    // 哈希表中记录的节点标记为删除
node.deleted = true // 当前节点标记为删除
} else {
exprToNode[subTreeExpr] = node
}

return node.name + subTreeExpr
}
for _, son := range root.son {
genExpr(son)
}

// 在字典树上回溯，仅访问未被删除的节点，并将路径记录到答案中
// 类似 257. 二叉树的所有路径
path := []string{}
var dfs func(*trieNode)
dfs = func(node *trieNode) {
if node.deleted {
return
}
path = append(path, node.name)
ans = append(ans, slices.Clone(path))
for _, son := range node.son {
dfs(son)
}
path = path[:len(path)-1] // 恢复现场
}
for _, son := range root.son {
dfs(son)
}
return
}

复杂度分析

• 时间复杂度：$\mathcal{O}(\ell\cdot m\log m)$，其中 $m$ 是字符串的总个数，$\ell\le 10$ 是单个字符串的长度，题目保证 $\ell\cdot m\le 2\cdot 10^5$。瓶颈在排序上。字符串拼接的复杂度是 $\mathcal{O}(\ell\cdot m)$。
  • 排序：最坏情况下一个节点有 $\mathcal{O}(m)$ 个儿子，我们会对 $\mathcal{O}(m)$ 个字符串排序。会发生 $\mathcal{O}(m\log m)$ 次字符串比较，每次 $\mathcal{O}(\ell)$ 时间，所以排序的时间复杂度为 $\mathcal{O}(\ell\cdot m\log m)$。
  • 字符串拼接：可能读者会认为当树退化成链时，代码会跑到 $\mathcal{O}((\ell\cdot m)^2)$ 时间，但这是不可能的。注意题目的这句话：「对于不在根层级的任意文件夹，其父文件夹也会包含在输入中。」这意味着如果一棵树的高度是 $d$，那么至少要 $1+2+3+\cdots+d = \mathcal{O}(d^2)$ 个字符串才能生成这棵树（可以参考示例 2），所以树的高度只有 $\mathcal{O}(\sqrt m)$。相应地，代码中的 node.name + subTreeExpr 会对长为 $\mathcal{O}(\ell\sqrt m)$ 的字符串复制拼接 $\mathcal{O}(\sqrt m)$ 次，所以时间复杂度为 $\mathcal{O}(\ell(\sqrt m)^2) = \mathcal{O}(\ell\cdot m)$。
• 空间复杂度：$\mathcal{O}(\ell\cdot m)$。

专题训练

• 297. 二叉树的序列化与反序列化
• 下面数据结构题单的「六、字典树（trie）」。

分类题单

如何科学刷题？

1. 滑动窗口与双指针（定长/不定长/单序列/双序列/三指针/分组循环）
2. 二分算法（二分答案/最小化最大值/最大化最小值/第K小）
3. 单调栈（基础/矩形面积/贡献法/最小字典序）
4. 网格图（DFS/BFS/综合应用）
5. 位运算（基础/性质/拆位/试填/恒等式/思维）
6. 图论算法（DFS/BFS/拓扑排序/基环树/最短路/最小生成树/网络流）
7. 动态规划（入门/背包/划分/状态机/区间/状压/数位/数据结构优化/树形/博弈/概率期望）
8. 常用数据结构（前缀和/差分/栈/队列/堆/字典树/并查集/树状数组/线段树）
9. 数学算法（数论/组合/概率期望/博弈/计算几何/随机算法）
10. 贪心与思维（基本贪心策略/反悔/区间/字典序/数学/思维/脑筋急转弯/构造）
11. 链表、二叉树与回溯（前后指针/快慢指针/DFS/BFS/直径/LCA/一般树）
12. 字符串（KMP/Z函数/Manacher/字符串哈希/AC自动机/后缀数组/子序列自动机）

我的题解精选（已分类）

欢迎关注 B站@灵茶山艾府

如果 $B$ 是 $A$ 的子文件夹，那么：

• $A + \texttt{/}$ 是 $B$ 的前缀。

比如 $\texttt{/a/b}$ 是 $\texttt{/a}$ 的子文件夹，其中 $\texttt{/a/}$ 是 $\texttt{/a/b}$ 的前缀。（当然，$\texttt{/a}$ 也是 $\texttt{/a/b}$ 的前缀。）

暴力的想法是，枚举路径 $B$，枚举其他路径 $A$，判断是否满足上述要求，这需要 $\mathcal{O}(\ell\cdot n^2)$ 时间，其中 $\ell\le 100$ 为单个字符串的长度。这太慢了。

可以不枚举 $A$ 吗？

如果 $\textit{folder}$ 列表是有序的（按照字典序从小到大排序），那么当 $B$ 是 $A$ 的子文件夹时，$A$ 是 $B$ 的前缀，所以 $A$ 一定排在 $B$ 的左边。

比如 $\textit{folder} = [\texttt{/a},\texttt{/a/b},\texttt{/c},\texttt{/d}]$：

1. $\texttt{/a}$ 不可能是任何文件夹 $A$ 的子文件夹（否则 $A$ 会排在 $\texttt{/a}$ 前面）。
2. $\texttt{/a/b}$ 是 $\texttt{/a}$ 的子文件夹，删除。
3. $\texttt{/c}$ 不是 $\texttt{/a}$ 的子文件夹。
4. $\texttt{/d}$ 不是 $\texttt{/c}$ 的子文件夹。注意，不需要判断 $\texttt{/d}$ 是否为 $\texttt{/a}$ 的子文件夹。因为一定不是，为什么？如果 $\texttt{/d}$ 是 $\texttt{/a}$ 的子文件夹，由于列表是有序的，$\texttt{/a}$ 的下一个字符串到 $\texttt{/d}$ 之间的字符串都是以 $\texttt{/a/}$ 开头的，所以上一个文件夹 $\texttt{/c}$ 也是以 $\texttt{/a/}$ 开头的，一定是 $\texttt{/a}$ 的子文件夹，一定会被删除，但这与实际矛盾。

因此，排序后，只需比较当前路径与上一个未被删除的路径。

代码实现时，为避免 $A + \texttt{/}$ 生成新字符串花费额外时间和空间，判断 $A + \texttt{/}$ 是否为 $B$ 的前缀，可以分解为：

1. 判断 $A$ 是否为 $B$ 的前缀。
2. 判断 $B[m]$ 是否为 $\texttt{/}$，其中 $m$ 是 $A$ 的长度。注意题目保证所有字符串互不相同，所以如果 $A$ 是 $B$ 的前缀，那么 $B$ 的长度一定大于 $A$ 的长度。所以 $B[m]$ 不会下标越界。

###py

class Solution:
    def removeSubfolders(self, folder: List[str]) -> List[str]:
        folder.sort()
        ans = [folder[0]]
        for s in folder[1:]:  # 切片可以用 for i in range(1, n) 代替，做到 O(1) 空间
            last = ans[-1]
            if not s.startswith(last) or s[len(last)] != '/':
                ans.append(s)
        return ans

###java

class Solution {
    public List<String> removeSubfolders(String[] folder) {
        Arrays.sort(folder);
        List<String> ans = new ArrayList<>();
        ans.add(folder[0]);
        for (int i = 1; i < folder.length; i++) {
            String s = folder[i];
            String last = ans.getLast();
            if (!s.startsWith(last) || s.charAt(last.length()) != '/') {
                ans.add(s);
            }
        }
        return ans;
    }
}

###cpp

class Solution {
public:
    vector<string> removeSubfolders(vector<string>& folder) {
        ranges::sort(folder);
        vector<string> ans = {folder[0]};
        for (int i = 1; i < folder.size(); i++) {
            string& s = folder[i];
            string& last = ans.back();
            if (!s.starts_with(last) || s[last.size()] != '/') {
                ans.emplace_back(s);
            }
        }
        return ans;
    }
};

###c

int cmp(const void* a, const void* b) {
    return strcmp(*(char**)a, *(char**)b);
}

char** removeSubfolders(char** folder, int folderSize, int* returnSize) {
    qsort(folder, folderSize, sizeof(char*), cmp);

    *returnSize = 1;
    for (int i = 1; i < folderSize; i++) {
        char* s = folder[i];
        char* last = folder[*returnSize - 1];
        int len = strlen(last);
        if (strncmp(last, s, len) != 0 || s[len] != '/') {
            folder[(*returnSize)++] = s; // 原地保存
        }
    }

    return folder;
}

###go

func removeSubfolders(folder []string) []string {
    slices.Sort(folder)
    ans := folder[:1]
    for _, s := range folder[1:] {
        last := ans[len(ans)-1]
        if !strings.HasPrefix(s, last) || s[len(last)] != '/' {
            ans = append(ans, s)
        }
    }
    return ans
}

###js

var removeSubfolders = function(folder) {
    folder.sort();
    const ans = [folder[0]];
    for (let i = 1; i < folder.length; i++) {
        const s = folder[i];
        const last = ans[ans.length - 1];
        if (!s.startsWith(last) || s[last.length] !== '/') {
            ans.push(s);
        }
    }
    return ans;
};

###rust

impl Solution {
    pub fn remove_subfolders(mut folder: Vec<String>) -> Vec<String> {
        folder.sort_unstable();
        let mut ans = vec![folder[0].clone()];
        for s in folder.into_iter().skip(1) {
            let last = ans.last().unwrap();
            if !s.starts_with(last) || s.as_bytes()[last.len()] != b'/' {
                ans.push(s);
            }
        }
        ans
    }
}

复杂度分析

• 时间复杂度：$\mathcal{O}(\ell\cdot n\log n)$ 时间，$n$ 是 $\textit{folder}$ 的长度，$\ell\le 100$ 为单个字符串的长度。排序有 $\mathcal{O}(n\log n)$ 次比较，每次 $\mathcal{O}(\ell)$ 时间。
• 空间复杂度：$\mathcal{O}(1)$。返回值不计入。忽略排序的栈开销。

分类题单

如何科学刷题？

1. 滑动窗口与双指针（定长/不定长/单序列/双序列/三指针/分组循环）
2. 二分算法（二分答案/最小化最大值/最大化最小值/第K小）
3. 单调栈（基础/矩形面积/贡献法/最小字典序）
4. 网格图（DFS/BFS/综合应用）
5. 位运算（基础/性质/拆位/试填/恒等式/思维）
6. 图论算法（DFS/BFS/拓扑排序/基环树/最短路/最小生成树/网络流）
7. 动态规划（入门/背包/划分/状态机/区间/状压/数位/数据结构优化/树形/博弈/概率期望）
8. 常用数据结构（前缀和/差分/栈/队列/堆/字典树/并查集/树状数组/线段树）
9. 数学算法（数论/组合/概率期望/博弈/计算几何/随机算法）
10. 贪心与思维（基本贪心策略/反悔/区间/字典序/数学/思维/脑筋急转弯/构造）
11. 链表、二叉树与回溯（前后指针/快慢指针/DFS/BFS/直径/LCA/一般树）
12. 字符串（KMP/Z函数/Manacher/字符串哈希/AC自动机/后缀数组/子序列自动机）

我的题解精选（已分类）

欢迎关注 B站@灵茶山艾府

题意：把 $\textit{nums}$ 分割成两部分，第一部分选 $n$ 个数求和，记作 $s_1$，第二部分选 $n$ 个数求和，记作 $s_2$。计算 $s_1-s_2$ 的最小值。

由于 $s_1$ 和 $s_2$ 互相独立，为了让 $s_1-s_2$ 尽量小，那么 $s_1$ 越小越好，$s_2$ 越大越好。

枚举分割位置，保证两部分都至少有 $n$ 个数。对于每个分割位置，计算最小 $s_1$ 和最大 $s_2$，所有 $s_1-s_2$ 的最小值就是答案。

一个 $n=4$ 的例子：

具体地，我们需要计算出 $\textit{nums}$ 的前缀最小和 $\textit{preMin}[i]$，即 $\textit{nums}[0]$ 到 $\textit{nums}[i]$ 中最小的 $n$ 个元素之和；以及后缀最大和 $\textit{sufMax}[i]$，即 $\textit{nums}[i]$ 到 $\textit{nums}[3n-1]$ 中最大的 $n$ 个元素之和。答案为 $\textit{preMin}[i]-\textit{sufMax}[i+1]$ 中的最小值。

对于后缀最大和，可以从右往左遍历 $\textit{nums}$ 计算，思路同经典题 703. 数据流中的第 K 大元素（Top K），维护一个包含 $n$ 个元素的最小堆（及其元素和）。不断向左遍历 $\textit{nums}$ 中的元素 $v$，若 $v$ 比堆顶元素大，则弹出堆顶，并将 $v$ 入堆，这可以让堆中元素和更大。

同理，对于前缀最小和，则需要维护一个包含 $n$ 个元素的最大堆（及其元素和）。不断向右遍历 $\textit{nums}$ 中的元素 $v$，若 $v$ 比堆顶元素小，则弹出堆顶，并将 $v$ 入堆，这可以让堆中元素和更小。

代码实现时，可以在计算前缀最小和的同时计算答案。

class Solution:
    def minimumDifference(self, nums: List[int]) -> int:
        m = len(nums)
        n = m // 3
        min_h = nums[-n:]
        heapify(min_h)

        suf_max = [0] * (m - n + 1)  # 后缀最大和
        suf_max[-1] = sum(min_h)
        for i in range(m - n - 1, n - 1, -1):
            suf_max[i] = suf_max[i + 1] + nums[i] - heappushpop(min_h, nums[i])

        max_h = [-x for x in nums[:n]]  # 所有元素取反，表示最大堆
        heapify(max_h)

        pre_min = -sum(max_h)  # 前缀最小和
        ans = pre_min - suf_max[n]  # i=n-1 时的答案
        for i in range(n, m - n):
            pre_min += nums[i] + heappushpop(max_h, -nums[i])
            ans = min(ans, pre_min - suf_max[i + 1])
        return ans

class Solution {
    public long minimumDifference(int[] nums) {
        int m = nums.length;
        int n = m / 3;
        PriorityQueue<Integer> minPQ = new PriorityQueue<>();
        long sum = 0;
        for (int i = m - 1; i >= m - n; i--) {
            minPQ.offer(nums[i]);
            sum += nums[i];
        }

        long[] sufMax = new long[m - n + 1]; // 后缀最大和
        sufMax[m - n] = sum;
        for (int i = m - n - 1; i >= n; i--) {
            int v = nums[i];
            if (v > minPQ.peek()) {
                sum += v - minPQ.poll();
                minPQ.offer(v);
            }
            sufMax[i] = sum;
        }

        PriorityQueue<Integer> maxPQ = new PriorityQueue<>((a, b) -> b - a);
        long preMin = 0; // 前缀最小和
        for (int i = 0; i < n; ++i) {
            maxPQ.offer(nums[i]);
            preMin += nums[i];
        }

        long ans = preMin - sufMax[n]; // i=n-1 时的答案
        for (int i = n; i < m - n; i++) {
            int v = nums[i];
            if (v < maxPQ.peek()) {
                preMin += v - maxPQ.poll();
                maxPQ.offer(v);
            }
            ans = Math.min(ans, preMin - sufMax[i + 1]);
        }
        return ans;
    }
}

class Solution {
public:
    long long minimumDifference(vector<int>& nums) {
        int m = nums.size(), n = m / 3;

        priority_queue<int, vector<int>, greater<>> min_pq(nums.end() - n, nums.end());
        long long sum = reduce(nums.end() - n, nums.end(), 0LL);

        vector<long long> suf_max(m - n + 1); // 后缀最大和
        suf_max[m - n] = sum;
        for (int i = m - n - 1; i >= n; i--) {
            int v = nums[i];
            if (v > min_pq.top()) {
                sum += v - min_pq.top();
                min_pq.pop();
                min_pq.push(v);
            }
            suf_max[i] = sum;
        }

        priority_queue<int> max_pq(nums.begin(), nums.begin() + n);
        long long pre_min = reduce(nums.begin(), nums.begin() + n, 0LL); // 前缀最小和

        long long ans = pre_min - suf_max[n]; // i=n-1 时的答案
        for (int i = n; i < m - n; i++) {
            int v = nums[i];
            if (v < max_pq.top()) {
                pre_min += v - max_pq.top();
                max_pq.pop();
                max_pq.push(v);
            }
            ans = min(ans, pre_min - suf_max[i + 1]);
        }
        return ans;
    }
};

func minimumDifference(nums []int) int64 {
m := len(nums)
n := m / 3
minH := minHeap{nums[m-n:]}
heap.Init(&minH)
sum := 0
for _, v := range nums[m-n:] {
sum += v
}

sufMax := make([]int, m-n+1) // 后缀最大和
sufMax[m-n] = sum
for i := m - n - 1; i >= n; i-- {
if v := nums[i]; v > minH.IntSlice[0] {
sum += v - minH.IntSlice[0]
minH.IntSlice[0] = v
heap.Fix(&minH, 0)
}
sufMax[i] = sum
}

maxH := maxHeap{nums[:n]}
heap.Init(&maxH)
preMin := 0 // 前缀最小和
for _, v := range nums[:n] {
preMin += v
}

ans := preMin - sufMax[n]
for i := n; i < m-n; i++ { // i=n-1 时的答案
if v := nums[i]; v < maxH.IntSlice[0] {
preMin += v - maxH.IntSlice[0]
maxH.IntSlice[0] = v
heap.Fix(&maxH, 0)
}
ans = min(ans, preMin-sufMax[i+1])
}
return int64(ans)
}

type minHeap struct{ sort.IntSlice }
func (minHeap) Push(any) {}
func (minHeap) Pop() (_ any) { return }

type maxHeap struct{ sort.IntSlice }
func (h maxHeap) Less(i, j int) bool { return h.IntSlice[i] > h.IntSlice[j] }
func (maxHeap) Push(any) {}
func (maxHeap) Pop() (_ any) { return }

复杂度分析

• 时间复杂度：$\mathcal{O}(n\log n)$。其中 $n$ 是 $\textit{nums}$ 的长度。
• 空间复杂度：$\mathcal{O}(n)$。

专题训练

下面动态规划题单的「专题：前后缀分解」。

分类题单

如何科学刷题？

1. 滑动窗口与双指针（定长/不定长/单序列/双序列/三指针/分组循环）
2. 二分算法（二分答案/最小化最大值/最大化最小值/第K小）
3. 单调栈（基础/矩形面积/贡献法/最小字典序）
4. 网格图（DFS/BFS/综合应用）
5. 位运算（基础/性质/拆位/试填/恒等式/思维）
6. 图论算法（DFS/BFS/拓扑排序/基环树/最短路/最小生成树/网络流）
7. 动态规划（入门/背包/划分/状态机/区间/状压/数位/数据结构优化/树形/博弈/概率期望）
8. 常用数据结构（前缀和/差分/栈/队列/堆/字典树/并查集/树状数组/线段树）
9. 数学算法（数论/组合/概率期望/博弈/计算几何/随机算法）
10. 贪心与思维（基本贪心策略/反悔/区间/字典序/数学/思维/脑筋急转弯/构造）
11. 链表、二叉树与回溯（前后指针/快慢指针/DFS/BFS/直径/LCA/一般树）
12. 字符串（KMP/Z函数/Manacher/字符串哈希/AC自动机/后缀数组/子序列自动机）

我的题解精选（已分类）

欢迎关注 B站@灵茶山艾府

分析

对于等式

$$
(a+b)\bmod k = (b+c)\bmod k
$$

根据 模运算的世界：当加减乘除遇上取模，可以移项，得

$$
(a+b-(b+c)) \bmod k = 0
$$

化简得

$$
(a-c)\bmod k = 0
$$

这意味着 $a$ 与 $c$ 关于模 $k$ 同余。即题目式子中的 $\textit{sub}[i]$ 与 $\textit{sub}[i+2]$ 关于模 $k$ 同余。换句话说，有效子序列的偶数项 $\textit{sub}[0],\textit{sub}[2],\textit{sub}[4],\ldots$ 都关于模 $k$ 同余，奇数项 $\textit{sub}[1],\textit{sub}[3],\textit{sub}[5],\ldots$ 都关于模 $k$ 同余。

如果把每个 $\textit{nums}[i]$ 都改成 $\textit{nums}[i]\bmod k$，问题等价于：

• 求最长子序列的长度，该子序列的奇数项都相同，偶数项都相同。

方法一：考察子序列的最后两项

比如 $\textit{nums}=[1,2,1,2,1,2]$：

• 遍历到 $1$ 的时候，在「末尾为 $1,2$ 的子序列」的末尾添加一个 $1$，得到「末尾为 $2,1$ 的子序列」。
• 遍历到 $2$ 的时候，在「末尾为 $2,1$ 的子序列」的末尾添加一个 $2$，得到「末尾为 $1,2$ 的子序列」。

从左到右遍历 $\textit{nums}$，遍历的同时，维护一个二维数组 $f[y][x]$，表示最后两项模 $k$ 分别为 $y$ 和 $x$ 的子序列的长度。

对于 $x=\textit{nums}[i]\bmod k$，我们可以在「最后两项模 $k$ 分别为 $x$ 和 $y$ 的子序列」的末尾添加 $\textit{nums}[i]$，那么「最后两项模 $k$ 分别为 $y$ 和 $x$ 的子序列」的长度会增加 $1$，即

$$
f[y][x] = f[x][y] + 1
$$

最后答案为 $f[i][j]$ 的最大值。

答疑

问：如何理解这个递推？它和记忆化搜索的区别是什么？

答：对比二者的计算顺序。如果用记忆化搜索来做，需要单独计算「最左（或者最右）两项模 $k$ 分别为 $x$ 和 $y$ 的子序列」的长度，这是「单线程」，必须查找下一个元素的位置。而递推的计算顺序是，（假设我们先遍历到了元素 $2$，然后遍历到了元素 $4$，两个元素属于不同的子序列）一会计算一下「最后两项模 $k$ 分别为 $y$ 和 $2$ 的子序列」，一会又计算一下「最后两项模 $k$ 分别为 $y$ 和 $4$ 的子序列」，这是「多线程」，没有查找元素位置的过程，遇到谁就处理谁。

具体请看 视频讲解 第三题，欢迎点赞关注~

###py

class Solution:
    def maximumLength(self, nums: List[int], k: int) -> int:
        f = [[0] * k for _ in range(k)]
        for x in nums:
            x %= k
            for y, fxy in enumerate(f[x]):
                f[y][x] = fxy + 1
        return max(map(max, f))

###py

class Solution:
    def maximumLength(self, nums: List[int], k: int) -> int:
        f = [0] * (k * k)
        for x in nums:
            x %= k
            # f[x * k: (x + 1) * k] 是二维写法的第 x 行
            # f[x::k] 是二维写法的第 x 列
            f[x::k] = [v + 1 for v in f[x * k: (x + 1) * k]]
        return max(f)

###java

class Solution {
    public int maximumLength(int[] nums, int k) {
        int ans = 0;
        int[][] f = new int[k][k];
        for (int x : nums) {
            x %= k;
            for (int y = 0; y < k; y++) {
                f[y][x] = f[x][y] + 1;
                ans = Math.max(ans, f[y][x]);
            }
        }
        return ans;
    }
}

###cpp

class Solution {
public:
    int maximumLength(vector<int>& nums, int k) {
        int ans = 0;
        vector f(k, vector<int>(k));
        for (int x : nums) {
            x %= k;
            for (int y = 0; y < k; y++) {
                f[y][x] = f[x][y] + 1;
                ans = max(ans, f[y][x]);
            }
        }
        return ans;
    }
};

###go

func maximumLength(nums []int, k int) (ans int) {
f := make([][]int, k)
for i := range f {
f[i] = make([]int, k)
}
for _, x := range nums {
x %= k
for y, fxy := range f[x] {
f[y][x] = fxy + 1
ans = max(ans, f[y][x])
}
}
return
}

复杂度分析

• 时间复杂度：$\mathcal{O}(k^2 + nk)$，其中 $n$ 是 $\textit{nums}$ 的长度。注意创建大小为 $k^2$ 的二维数组需要 $\mathcal{O}(k^2)$ 的时间。
• 空间复杂度：$\mathcal{O}(k^2)$。

方法二：枚举余数，考察子序列的最后一项

枚举子序列相邻两项之和模 $k$ 的结果为 $m=0,1,2,\ldots, k-1$。

如果知道了子序列的最后一项（假设是 $x$），那么子序列的倒数第二项也就确定了，根据 模运算的世界：当加减乘除遇上取模，倒数第二项为

$$
(m - x\bmod k + k) \bmod k
$$

加 $k$ 再模 $k$ 是为了在 $m < x\bmod k$ 时，保证计算结果非负。

类似方法一，从左到右遍历 $\textit{nums}$ 的同时，维护一个数组 $f[x]$，表示最后一项模 $k$ 为 $x$ 的子序列的长度。

对于 $x=\textit{nums}[i]\bmod k$，我们可以在「最后一项模 $k$ 为 $(m - x\bmod k + k) \bmod k$ 的子序列」的末尾添加 $\textit{nums}[i]$，那么「最后一项模 $k$ 为 $x$ 的子序列」的长度会增加 $1$，即

$$
f[x] = f[(m - x\bmod k + k) \bmod k] + 1
$$

Python 取模更简单，由于允许负数下标，可以直接用 $f[m-x\bmod k]$ 作为转移来源。

遍历结束后（或者遍历中），用 $f[i]$ 更新答案的最大值。

###py

class Solution:
    def maximumLength(self, nums: List[int], k: int) -> int:
        ans = 0
        for m in range(k):
            f = [0] * k
            for x in nums:
                x %= k
                f[x] = f[m - x] + 1
            ans = max(ans, max(f))
        return ans

###java

class Solution {
    public int maximumLength(int[] nums, int k) {
        int ans = 0;
        for (int m = 0; m < k; m++) {
            int[] f = new int[k];
            for (int x : nums) {
                x %= k;
                f[x] = f[(m - x + k) % k] + 1;
                ans = Math.max(ans, f[x]);
            }
        }
        return ans;
    }
}

###cpp

class Solution {
public:
    int maximumLength(vector<int>& nums, int k) {
        int ans = 0;
        for (int m = 0; m < k; m++) {
            vector<int> f(k);
            for (int x : nums) {
                x %= k;
                f[x] = f[(m - x + k) % k] + 1;
                ans = max(ans, f[x]);
            }
        }
        return ans;
    }
};

###go

func maximumLength(nums []int, k int) (ans int) {
f := make([]int, k)
for m := 0; m < k; m++ {
clear(f)
for _, x := range nums {
x %= k
f[x] = f[(m-x+k)%k] + 1
ans = max(ans, f[x])
}
}
return
}

复杂度分析

• 时间复杂度：$\mathcal{O}(k(k+n))$，其中 $n$ 是 $\textit{nums}$ 的长度。注意创建大小为 $k$ 的数组需要 $\mathcal{O}(k)$ 的时间。
• 空间复杂度：$\mathcal{O}(k)$。

专题训练

见动态规划题单的「§7.4 合法子序列 DP」。

分类题单

如何科学刷题？

1. 滑动窗口与双指针（定长/不定长/单序列/双序列/三指针/分组循环）
2. 二分算法（二分答案/最小化最大值/最大化最小值/第K小）
3. 单调栈（基础/矩形面积/贡献法/最小字典序）
4. 网格图（DFS/BFS/综合应用）
5. 位运算（基础/性质/拆位/试填/恒等式/思维）
6. 图论算法（DFS/BFS/拓扑排序/基环树/最短路/最小生成树/网络流）
7. 动态规划（入门/背包/划分/状态机/区间/状压/数位/数据结构优化/树形/博弈/概率期望）
8. 常用数据结构（前缀和/差分/栈/队列/堆/字典树/并查集/树状数组/线段树）
9. 数学算法（数论/组合/概率期望/博弈/计算几何/随机算法）
10. 贪心与思维（基本贪心策略/反悔/区间/字典序/数学/思维/脑筋急转弯/构造）
11. 链表、二叉树与回溯（前后指针/快慢指针/DFS/BFS/直径/LCA/一般树）
12. 字符串（KMP/Z函数/Manacher/字符串哈希/AC自动机/后缀数组/子序列自动机）

我的题解精选（已分类）

欢迎关注 B站@灵茶山艾府

本题和周赛第三题是一样的，令 $k=2$ 即可。请看 我的题解。