459. 重复的子字符串

给定一个非空的字符串 s ，检查是否可以通过由它的一个子串重复多次构成。

示例 1:

输入: s = “abab”
输出: true
解释: 可由子串 “ab” 重复两次构成。
示例 2:

输入: s = “aba”
输出: false
示例 3:

输入: s = “abcabcabcabc”
输出: true
解释: 可由子串 “abc” 重复四次构成。 (或子串 “abcabc” 重复两次构成。)

提示：

1 <= s.length <= 104
s 由小写英文字母组成

力扣459题-重复的子字符串，经典的字符串匹配问题！

def repeatedSubstringPattern(s: str) -> bool:
    """
    重复的子字符串 - 力扣459题
    
    给定一个非空字符串 s，检查它是否可以由它的一个子字符串重复多次构成。
    
    示例：
    输入: s = "abab"
    输出: True
    解释: 可由子字符串 "ab" 重复两次构成
    
    输入: s = "aba"
    输出: False
    解释: 无法由子字符串重复构成
    
    算法思路：字符串拼接技巧
    - 将 s 拼接成 s + s
    - 去掉首尾字符后，如果 s 仍在新字符串中，说明可以由子字符串重复构成
    
    时间复杂度：O(n)，空间复杂度：O(n)
    """
    
    # 核心思想：
    # 如果 s 可以由子字符串 t 重复构成，即 s = t + t + ... + t
    # 那么 s + s = t + t + ... + t + t + t + ... + t
    # 去掉首尾字符后，s 必然出现在中间部分
    return s in (s + s)[1:-1]


# ====== 详细注释版本 ======
def repeatedSubstringPattern_detailed(s: str) -> bool:
    """
    重复的子字符串 - 详细注释版本
    
    核心思想：
    如果 s = "nP"（n 个相同的模式 P 重复 n 次）
    那么 s + s = "nPnP" = "nPnP"
    去掉首尾字符后，s 必然出现在中间
    
    例如：s = "abab"
    s + s = "abababab"
    去掉首尾：(s + s)[1:-1] = "bababa"
    s = "abab" 在 "bababa" 中吗？是的！
    
    反例：s = "aba"
    s + s = "abaaba"
    去掉首尾：(s + s)[1:-1] = "baab"
    s = "aba" 在 "baab" 中吗？不是！
    """
    
    # 方法：将 s 拼接，去掉首尾，检查 s 是否在其中
    doubled = s + s
    trimmed = doubled[1:-1]  # 去掉首尾字符
    
    # 如果 s 可以由子字符串重复构成，s 必然出现在 trimmed 中
    return s in trimmed


# ====== 暴力解法 ======
def repeatedSubstringPattern_brute(s: str) -> bool:
    """
    重复的子字符串 - 暴力解法
    
    思路：
    - 枚举所有可能的子字符串长度（必须是 s 长度的因数）
    - 检查是否可以重复构成原字符串
    
    时间复杂度：O(n²)，空间复杂度：O(1)
    """
    
    n = len(s)
    
    # 子字符串长度必须是 n 的因数
    # 且长度不能等于 n（否则不是重复）
    for length in range(1, n // 2 + 1):
        # 检查长度是否是因数
        if n % length != 0:
            continue
        
        # 提取子字符串
        pattern = s[:length]
        
        # 检查是否可以重复构成
        if pattern * (n // length) == s:
            return True
    
    return False


# ====== 暴力解法 - 详细版本 ======
def repeatedSubstringPattern_brute_detailed(s: str) -> bool:
    """
    重复的子字符串 - 暴力解法详细版本
    
    详细步骤：
    1. 遍历所有可能的子字符串长度（1 到 n//2）
    2. 检查长度是否是字符串长度的因数
    3. 如果是，检查该长度的子字符串能否重复构成原字符串
    """
    
    n = len(s)
    
    # 子字符串长度从 1 到 n//2
    for length in range(1, n // 2 + 1):
        # 只有当长度是 n 的因数时才可能
        if n % length != 0:
            continue
        
        # 获取子字符串
        substring = s[:length]
        
        # 检查是否可以重复构成
        # 方法1：拼接检查
        reconstructed = substring * (n // length)
        if reconstructed == s:
            return True
        
        # 方法2：逐段检查（更清晰）
        # is_valid = True
        # for i in range(0, n, length):
        #     if s[i:i+length] != substring:
        #         is_valid = False
        #         break
        # if is_valid:
        #     return True
    
    return False


# ====== KMP算法 ======
def repeatedSubstringPattern_kmp(s: str) -> bool:
    """
    重复的子字符串 - KMP算法
    
    核心思想：
    - 利用 KMP 的 next 数组（部分匹配表）
    - 如果 s 可以由子字符串重复构成，那么：
      len(s) % (len(s) - next[len(s)-1]) == 0
    
    时间复杂度：O(n)，空间复杂度：O(n)
    """
    
    n = len(s)
    
    # 构建 next 数组
    # next[i] 表示 s[0...i] 的最长相等前后缀长度
    next_arr = [0] * n
    
    # 计算 next 数组
    j = 0
    for i in range(1, n):
        # 不匹配，回退
        while j > 0 and s[i] != s[j]:
            j = next_arr[j - 1]
        
        # 匹配，前进
        if s[i] == s[j]:
            j += 1
            next_arr[i] = j
    
    # 最长相等前后缀长度
    longest_prefix_suffix = next_arr[-1]
    
    # 如果最长前后缀长度为0，说明不能重复构成
    if longest_prefix_suffix == 0:
        return False
    
    # 检查是否可以整除
    # 子字符串长度 = n - longest_prefix_suffix
    substring_length = n - longest_prefix_suffix
    
    return n % substring_length == 0


# ====== KMP算法 - 详细版本 ======
def repeatedSubstringPattern_kmp_detailed(s: str) -> bool:
    """
    重复的子字符串 - KMP算法详细版本
    
    原理解释：
    
    假设 s = "ababab"，n = 6
    
    next 数组计算过程：
    - next[0] = 0（单个字符没有前后缀）
    - next[1] = 0（'b' != 'a'）
    - next[2] = 1（'a' == 'a'）
    - next[3] = 2（'b' == 'b'）
    - next[4] = 3（'a' == 'a'）
    - next[5] = 4（'b' == 'b'）
    
    next = [0, 0, 1, 2, 3, 4]
    
    最长相等前后缀长度 = next[5] = 4
    
    子字符串长度 = 6 - 4 = 2
    
    6 % 2 == 0，返回 True
    """
    
    n = len(s)
    
    # 特殊情况
    if n <= 1:
        return False
    
    # ====== Step 1: 构建 next 数组 ======
    next_arr = [0] * n
    j = 0  # 当前匹配的前缀长度
    
    for i in range(1, n):
        # 不匹配时，回退到上一个匹配位置
        while j > 0 and s[i] != s[j]:
            j = next_arr[j - 1]
        
        # 匹配时，前进
        if s[i] == s[j]:
            j += 1
            next_arr[i] = j
    
    # ====== Step 2: 检查是否可以重复构成 ======
    longest = next_arr[-1]
    
    # 如果没有相等前后缀，不能重复构成
    if longest == 0:
        return False
    
    # 计算最小重复单元长度
    min_unit_length = n - longest
    
    # 检查是否可以整除
    return n % min_unit_length == 0


# ====== 测试用例 ======
if __name__ == "__main__":
    # ====== 测试用例 1：基本示例 ======
    s1 = "abab"
    result1 = repeatedSubstringPattern(s1)
    print(f"测试1: 输入 '{s1}'")
    print(f"      输出 {result1}")
    print(f"      预期 True")
    print(f"      解释: 可由 'ab' 重复2次构成")
    print()
    
    # ====== 测试用例 2：不可重复 ======
    s2 = "aba"
    result2 = repeatedSubstringPattern(s2)
    print(f"测试2: 输入 '{s2}'")
    print(f"      输出 {result2}")
    print(f"      预期 False")
    print()
    
    # ====== 测试用例 3：三个重复 ======
    s3 = "abcabcabc"
    result3 = repeatedSubstringPattern(s3)
    print(f"测试3: 输入 '{s3}'")
    print(f"      输出 {result3}")
    print(f"      预期 True")
    print(f"      解释: 可由 'abc' 重复3次构成")
    print()
    
    # ====== 测试用例 4：全部相同 ======
    s4 = "aaaa"
    result4 = repeatedSubstringPattern(s4)
    print(f"测试4: 输入 '{s4}'")
    print(f"      输出 {result4}")
    print(f"      预期 True")
    print(f"      解释: 可由 'a' 重复4次构成")
    print()
    
    # ====== 测试用例 5：单字符 ======
    s5 = "a"
    result5 = repeatedSubstringPattern(s5)
    print(f"测试5: 输入 '{s5}'")
    print(f"      输出 {result5}")
    print(f"      预期 False")
    print(f"      解释: 单个字符无法重复构成")
    print()
    
    # ====== 测试用例 6：两个相同字符 ======
    s6 = "aa"
    result6 = repeatedSubstringPattern(s6)
    print(f"测试6: 输入 '{s6}'")
    print(f"      输出 {result6}")
    print(f"      预期 True")
    print()
    
    # ====== 测试用例 7：两个不同字符 ======
    s7 = "ab"
    result7 = repeatedSubstringPattern(s7)
    print(f"测试7: 输入 '{s7}'")
    print(f"      输出 {result7}")
    print(f"      预期 False")
    print()
    
    # ====== 测试用例 8：验证字符串拼接方法 ======
    s8 = "abab"
    doubled = s8 + s8
    trimmed = doubled[1:-1]
    print(f"测试8: 验证字符串拼接方法")
    print(f"      s = '{s8}'")
    print(f"      s + s = '{doubled}'")
    print(f"      去掉首尾 = '{trimmed}'")
    print(f"      '{s8}' in '{trimmed}'? {s8 in trimmed}")
    print()
    
    # ====== 测试用例 9：验证KMP ======
    s9 = "ababab"
    result9 = repeatedSubstringPattern_kmp_detailed(s9)
    print(f"测试9: KMP方法 - 输入 '{s9}'")
    print(f"      输出 {result9}")
    print(f"      预期 True")
    print()
    
    # ====== 测试用例 10：复杂示例 ======
    s10 = "abcab"
    result10 = repeatedSubstringPattern(s10)
    print(f"测试10: 输入 '{s10}'")
    print(f"       输出 {result10}")
    print(f"       预期 False")

详细解释

题目理解

要求：

• 判断字符串是否可以由子字符串重复多次构成
• 子字符串至少重复两次

示例：

"abab" → True（"ab" × 2）
"abcabc" → True（"abc" × 2）
"aba" → False（无法重复构成）
"aaaa" → True（"a" × 4）

方法一：字符串拼接技巧（推荐）

核心思想：
如果 s 可以由子字符串重复构成，那么：

s = "abab"
s + s = "abababab"
去掉首尾 = "bababa"
s 在其中吗？是的！

原理图解：

假设 s = "abab" = "ab" × 2

s + s = "abab" + "abab" = "abababab"
         ^^^^    ^^^^
         第一份  第二份

去掉首尾字符：
"abababab"[1:-1] = "bababa"
                   ^^^^
                   这部分包含完整的 s

为什么？
因为 s 重复了多次，去掉首尾后，中间部分必然包含完整的 s

反例：

s = "aba"（不能重复构成）

s + s = "abaaba"
去掉首尾 = "baab"
s = "aba" 在 "baab" 中吗？不是！

说明无法重复构成

方法二：暴力枚举

思路：

1. 枚举所有可能的子字符串长度（1 到 n//2）
2. 检查长度是否是字符串长度的因数
3. 检查该长度的子字符串能否重复构成原字符串

关键点：

• 子字符串长度必须是 len(s) 的因数
• 如果 len(s) = 6，可能的子字符串长度为 1, 2, 3

for length in range(1, n // 2 + 1):
    if n % length != 0:
        continue
    
    substring = s[:length]
    if substring * (n // length) == s:
        return True

方法三：KMP算法（进阶）

核心概念：next 数组

next[i] 表示 s[0...i] 的最长相等前后缀长度。

示例：

s = "ababab"
索引: 0 1 2 3 4 5
字符: a b a b a b
next: 0 0 1 2 3 4

解释：
- next[2] = 1: "aba" 的最长相等前后缀是 "a"，长度为1
- next[4] = 3: "ababa" 的最长相等前后缀是 "aba"，长度为3

关键公式：

如果 s 可以由子字符串重复构成：
子字符串长度 = n - next[n-1]
且 n % (n - next[n-1]) == 0

原理：

s = "ababab", n = 6
next[5] = 4（最长相等前后缀长度）

子字符串长度 = 6 - 4 = 2

6 % 2 == 0，返回 True

图解：
"ababab"
 ^^^^  ← 前缀 "abab"
      ^^^^  ← 后缀 "abab"
      
最长相等前后缀 = 4

去掉重复部分，剩余 = 6 - 4 = 2（"ab"）

如果可以整除，说明可以重复构成

三种方法对比

方法	时间复杂度	空间复杂度	难度
字符串拼接	O(n)	O(n)	⭐ 简单
暴力枚举	O(n²)	O(1)	⭐ 简单
KMP算法	O(n)	O(n)	⭐⭐⭐ 困难

字符串拼接方法详解

为什么去掉首尾？

如果不去掉首尾：
s = "abab"
s + s = "abababab"
s in (s + s) → True（但这是错的！）

因为 s + s 本来就包含 s 在开头！

去掉首尾后：
(s + s)[1:-1] = "bababa"
只检查中间部分，避免误判

完整推导：

设 s 可以由 t 重复 k 次构成（k ≥ 2）
s = t × k

s + s = t × k + t × k = t × 2k

去掉首尾后：
(s + s)[1:-1] = t × (2k - 2) + 部分t

由于 k ≥ 2，所以 2k - 2 ≥ k
因此 s = t × k 必然在其中

反证：
如果 s 不能由子字符串重复构成
那么 s + s 去掉首尾后，s 不会出现在中间

复杂度分析

字符串拼接方法：

• 时间：O(n) - in 操作是 O(n)
• 空间：O(n) - 创建了新字符串

暴力枚举：

• 时间：O(n²) - 最坏情况需要检查 n/2 个长度，每次检查 O(n)
• 空间：O(1)

KMP：

• 时间：O(n) - 构建 next 数组 + 检查
• 空间：O(n) - next 数组

特殊情况

情况	输入	输出	说明
单字符	"a"	False	不能重复
两个相同	"aa"	True	"a" × 2
两个不同	"ab"	False	不能重复
全相同	"aaaa"	True	"a" × 4
质数长度	"aba"	False	只能是本身

易错点总结

1. 单字符情况："a" 返回 False，不是 True
2. 字符串拼接去掉首尾：必须去掉，否则会误判
3. 暴力枚举因数：只检查因数长度
4. KMP的next数组：理解最长相等前后缀的含义

与其他题目的对比

题目	类型	关键区别
459-重复的子字符串	字符串匹配	检查重复构成
28-实现strStr()	KMP	子串匹配
686-重复叠加字符串匹配	字符串匹配	最少重复次数

这道题推荐使用字符串拼接技巧，简洁高效！理解"去掉首尾后 s 仍在其中"的原理就掌握了核心！🎯

1047. 删除字符串中的所有相邻重复项

给出由小写字母组成的字符串 s，重复项删除操作会选择两个相邻且相同的字母，并删除它们。

在 s 上反复执行重复项删除操作，直到无法继续删除。

在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。

示例：

输入：“abbaca”
输出：“ca”
解释：
例如，在 “abbaca” 中，我们可以删除 “bb” 由于两字母相邻且相同，这是此时唯一可以执行删除操作的重复项。之后我们得到字符串 “aaca”，其中又只有 “aa” 可以执行重复项删除操作，所以最后的字符串为 “ca”。

提示：

1 <= s.length <= 105
s 仅由小写英文字母组成。

力扣1047题-删除字符串中的所有相邻重复项，经典的栈应用题！

def removeDuplicates(s: str) -> str:
    """
    删除字符串中的所有相邻重复项 - 力扣1047题
    
    给出由小写字母组成的字符串 S，重复项删除操作会选择两个相邻且相同的字母，
    并删除它们。在 S 上反复执行重复项删除操作，直到无法继续删除。
    
    示例：
    输入: s = "abbaca"
    输出: "ca"
    解释:
    - 删除 "bb" → "aaca"
    - 删除 "aa" → "ca"
    
    算法思路：栈
    - 遍历字符串，将字符入栈
    - 如果当前字符与栈顶相同，弹出栈顶（相当于删除两个相邻重复项）
    - 否则，将当前字符入栈
    
    时间复杂度：O(n)，空间复杂度：O(n)
    """
    
    stack = []
    
    for char in s:
        # 如果栈不为空且栈顶元素等于当前字符
        if stack and stack[-1] == char:
            stack.pop()  # 弹出栈顶，相当于删除了一对相邻重复项
        else:
            stack.append(char)  # 否则入栈
    
    return ''.join(stack)


# ====== 详细注释版本 ======
def removeDuplicates_detailed(s: str) -> str:
    """
    删除字符串中的所有相邻重复项 - 详细注释版本
    
    核心思想：
    使用栈模拟"消消乐"过程
    - 栈顶元素就是"前一个字符"
    - 如果当前字符与栈顶相同，说明发现相邻重复，删除（弹出）
    - 否则，将当前字符入栈
    
    这就是栈的典型应用：处理相邻元素关系
    """
    
    # 初始化空栈
    stack = []
    
    # 遍历字符串中的每个字符
    for char in s:
        # 情况1：栈不为空 且 栈顶元素 == 当前字符
        # 说明发现了相邻重复项，需要删除
        if stack and stack[-1] == char:
            # 弹出栈顶元素
            # 这相当于删除了两个相邻重复项（栈顶 + 当前字符不入栈）
            popped = stack.pop()
            # Debug: print(f"删除相邻重复: {popped}{char}")
        
        # 情况2：栈为空 或 栈顶元素 != 当前字符
        # 没有相邻重复，将当前字符入栈
        else:
            stack.append(char)
            # Debug: print(f"入栈: {char}, 栈: {stack}")
    
    # 栈中剩下的字符就是最终结果
    return ''.join(stack)


# ====== 双指针解法（原地修改）======
def removeDuplicates_two_pointers(s: str) -> str:
    """
    删除字符串中的所有相邻重复项 - 双指针解法
    
    核心思想：
    使用双指针模拟栈操作
    - slow 指针指向"栈顶"位置
    - fast 指针遍历字符串
    
    时间复杂度：O(n)，空间复杂度：O(n) 或 O(1) 如果允许原地修改
    """
    
    # 将字符串转为列表（因为 Python 字符串不可变）
    chars = list(s)
    
    # slow 指针充当"栈顶"
    slow = 0
    
    # fast 指针遍历字符串
    for fast in range(len(chars)):
        # 如果栈不为空（slow > 0）且栈顶等于当前字符
        if slow > 0 and chars[slow - 1] == chars[fast]:
            # 弹出栈顶
            slow -= 1
        else:
            # 将当前字符入栈
            chars[slow] = chars[fast]
            slow += 1
    
    # 返回栈中字符
    return ''.join(chars[:slow])


# ====== 递归解法 ======
def removeDuplicates_recursive(s: str) -> str:
    """
    删除字符串中的所有相邻重复项 - 递归解法
    
    思路：
    - 找到第一对相邻重复项并删除
    - 递归处理剩余字符串
    - 直到没有相邻重复项
    
    注意：这种方法时间复杂度较高，不推荐
    时间复杂度：O(n²)，空间复杂度：O(n)
    """
    
    # 递归终止条件：没有相邻重复项
    n = len(s)
    for i in range(n - 1):
        if s[i] == s[i + 1]:
            # 找到相邻重复项，删除并递归
            new_s = s[:i] + s[i + 2:]
            return removeDuplicates_recursive(new_s)
    
    # 没有找到相邻重复项，返回原字符串
    return s


# ====== 迭代优化解法 ======
def removeDuplicates_iterative(s: str) -> str:
    """
    删除字符串中的所有相邻重复项 - 迭代优化版本
    
    思路：不断扫描字符串，删除相邻重复项，直到无法删除
    时间复杂度：O(n²)，不推荐
    """
    
    changed = True
    
    while changed:
        changed = False
        new_s = ""
        i = 0
        n = len(s)
        
        while i < n:
            # 检查是否有相邻重复
            if i + 1 < n and s[i] == s[i + 1]:
                # 跳过这两个字符
                i += 2
                changed = True
            else:
                new_s += s[i]
                i += 1
        
        s = new_s
    
    return s


# ====== 测试用例 ======
if __name__ == "__main__":
    # ====== 测试用例 1：基本示例 ======
    s1 = "abbaca"
    result1 = removeDuplicates(s1)
    print(f"测试1: 输入 '{s1}'")
    print(f"      输出 '{result1}'")
    print(f"      预期 'ca'")
    print(f"      过程: 'abbaca' → 删除'bb' → 'aaca' → 删除'aa' → 'ca'")
    print()
    
    # ====== 测试用例 2：无重复 ======
    s2 = "abcd"
    result2 = removeDuplicates(s2)
    print(f"测试2: 输入 '{s2}'")
    print(f"      输出 '{result2}'")
    print(f"      预期 'abcd'")
    print()
    
    # ====== 测试用例 3：全部删除 ======
    s3 = "aabbccdd"
    result3 = removeDuplicates(s3)
    print(f"测试3: 输入 '{s3}'")
    print(f"      输出 '{result3}'")
    print(f"      预期 ''（空字符串）")
    print()
    
    # ====== 测试用例 4：嵌套删除 ======
    s4 = "abccba"
    result4 = removeDuplicates(s4)
    print(f"测试4: 输入 '{s4}'")
    print(f"      输出 '{result4}'")
    print(f"      预期 ''")
    print(f"      过程: 'abccba' → 删除'cc' → 'abba' → 删除'bb' → 'aa' → 删除'aa' → ''")
    print()
    
    # ====== 测试用例 5：单字符 ======
    s5 = "a"
    result5 = removeDuplicates(s5)
    print(f"测试5: 输入 '{s5}'")
    print(f"      输出 '{result5}'")
    print(f"      预期 'a'")
    print()
    
    # ====== 测试用例 6：空字符串 ======
    s6 = ""
    result6 = removeDuplicates(s6)
    print(f"测试6: 输入 '{s6}'")
    print(f"      输出 '{result6}'")
    print(f"      预期 ''")
    print()
    
    # ====== 测试用例 7：多个相同字符 ======
    s7 = "aaaa"
    result7 = removeDuplicates(s7)
    print(f"测试7: 输入 '{s7}'")
    print(f"      输出 '{result7}'")
    print(f"      预期 ''")
    print()
    
    # ====== 测试用例 8：复杂嵌套 ======
    s8 = "abbbaa"
    result8 = removeDuplicates(s8)
    print(f"测试8: 输入 '{s8}'")
    print(f"      输出 '{result8}'")
    print(f"      过程: 'abbbaa' → 删除'bb' → 'abbaa' → 删除'bb' → 'aaa' → 删除'aa' → 'a'")
    print()
    
    # ====== 测试用例 9：验证双指针方法 ======
    s9 = "abbaca"
    result9 = removeDuplicates_two_pointers(s9)
    print(f"测试9: 双指针方法 - 输入 '{s9}'")
    print(f"      输出 '{result9}'")
    print(f"      预期 'ca'")
    print()
    
    # ====== 测试用例 10：验证递归方法 ======
    s10 = "abbaca"
    result10 = removeDuplicates_recursive(s10)
    print(f"测试10: 递归方法 - 输入 '{s10}'")
    print(f"       输出 '{result10}'")
    print(f"       预期 'ca'")

详细解释

题目理解

要求：

• 删除字符串中所有相邻的重复项
• 删除后可能产生新的相邻重复，需要继续删除
• 直到无法删除为止

示例详解：

输入: "abbaca"

步骤1: 发现 "bb" 是相邻重复
       删除 → "aaca"

步骤2: 发现 "aa" 是相邻重复
       删除 → "ca"

步骤3: 没有相邻重复，结束

输出: "ca"

算法核心：栈

为什么用栈？

• 栈可以记录"前一个字符"
• 栈顶元素就是最近处理的字符
• 如果当前字符与栈顶相同，说明发现相邻重复，弹出即可

执行过程图解

以 s = "abbaca" 为例：

初始状态
─────────────
栈: []
字符串: "abbaca"

步骤1: 处理 'a'
─────────────
栈为空，入栈
栈: [a]

步骤2: 处理 'b'
─────────────
栈顶 'a' ≠ 'b'，入栈
栈: [a, b]

步骤3: 处理 'b'
─────────────
栈顶 'b' == 'b'，弹出栈顶
栈: [a]

步骤4: 处理 'a'
─────────────
栈顶 'a' == 'a'，弹出栈顶
栈: []

步骤5: 处理 'c'
─────────────
栈为空，入栈
栈: [c]

步骤6: 处理 'a'
─────────────
栈顶 'c' ≠ 'a'，入栈
栈: [c, a]

最终结果: "ca"

复杂嵌套示例

以 s = "abccba" 为例：

步骤1: 'a' 入栈 → [a]
步骤2: 'b' 入栈 → [a, b]
步骤3: 'c' 入栈 → [a, b, c]
步骤4: 'c' == 栈顶 'c'，弹出 → [a, b]
步骤5: 'b' == 栈顶 'b'，弹出 → [a]
步骤6: 'a' == 栈顶 'a'，弹出 → []

结果: ""（全部删除）

代码逻辑拆解

def removeDuplicates(s: str) -> str:
    
    stack = []
    
    for char in s:
        # 情况1：发现相邻重复
        if stack and stack[-1] == char:
            stack.pop()  # 弹出栈顶（相当于删除两个字符）
        
        # 情况2：没有相邻重复
        else:
            stack.append(char)  # 入栈
    
    return ''.join(stack)

双指针解法详解

核心思想：

• 使用 slow 指针模拟栈顶
• 使用 fast 指针遍历字符串
• chars[0:slow] 就是"栈"中的内容

chars = list(s)
slow = 0  # 栈顶指针

for fast in range(len(chars)):
    # 如果栈不为空且栈顶 == 当前字符
    if slow > 0 and chars[slow - 1] == chars[fast]:
        slow -= 1  # 弹出栈顶
    else:
        chars[slow] = chars[fast]  # 入栈
        slow += 1

return ''.join(chars[:slow])

图解：

s = "abbaca"
chars = ['a', 'b', 'b', 'a', 'c', 'a']

fast=0: chars[0]='a', slow=0, 栈空，入栈
         chars = ['a', ...], slow=1

fast=1: chars[1]='b', chars[0]='a' ≠ 'b', 入栈
         chars = ['a', 'b', ...], slow=2

fast=2: chars[2]='b', chars[1]='b' == 'b', 弹出
         slow=1

fast=3: chars[3]='a', chars[0]='a' == 'a', 弹出
         slow=0

fast=4: chars[4]='c', 栈空，入栈
         chars = ['c', ...], slow=1

fast=5: chars[5]='a', chars[0]='c' ≠ 'a', 入栈
         chars = ['c', 'a', ...], slow=2

结果: chars[:2] = "ca"

复杂度分析

方法	时间复杂度	空间复杂度
栈方法	O(n)	O(n)
双指针	O(n)	O(n)
递归	O(n²)	O(n)

特殊情况处理

情况	输入	输出	说明
空字符串	""	""	无需处理
单字符	"a"	"a"	无法删除
全删除	"aabb"	""	全部配对
嵌套删除	"abccba"	""	连锁删除
无重复	"abcd"	"abcd"	保持原样

易错点总结

1. 栈的判断条件：先检查 stack 是否为空，再访问 stack[-1]
2. 删除逻辑：弹出栈顶 = 删除两个字符（栈顶 + 当前不入栈）
3. 最终结果：栈中所有字符按顺序拼接
4. 嵌套删除：删除后可能产生新的相邻重复，栈自动处理

与其他题目的对比

题目	类型	关键区别
1047-删除相邻重复项	栈	删除两个相同字符
1209-删除重复项II	栈	删除连续k个相同字符
316-去除重复字母	单调栈	保证字典序最小
71-简化路径	栈	路径处理

进阶：1209-删除重复项II（删除连续k个相同字符）

def removeDuplicates_II(s: str, k: int) -> str:
    """
    删除连续 k 个相同的字符
    """
    stack = []  # [(字符, 连续计数)]
    
    for char in s:
        if stack and stack[-1][0] == char:
            stack[-1] = (char, stack[-1][1] + 1)
        else:
            stack.append((char, 1))
        
        # 如果计数达到 k，删除
        if stack[-1][1] == k:
            stack.pop()
    
    return ''.join(char * count for char, count in stack)

# 测试
print(removeDuplicates_II("deeedbbcccbdaa", 3))  # "aa"

这道题推荐使用栈方法，简洁直观，就像"消消乐"游戏一样！理解"栈顶就是前一个字符"就掌握了核心！🎯