2025-11-08：不相交子字符串的最大数量。用go语言，给定字符串 word，求最多能从中取出多少个互不重叠的连续片段（即子

福大大架构师每日一题

发布于 2025-12-19 08:52:07

1420

文章被收录于专栏：福大大架构师每日一题福大大架构师每日一题

2025-11-08：不相交子字符串的最大数量。用go语言，给定字符串 word，求最多能从中取出多少个互不重叠的连续片段（即子串），要求每个片段长度不少于 4 且第一个字符和最后一个字符相同。返回这个最大数量。

1 <= word.length <= 200000。

word 仅由小写英文字母组成。

输入： word = "abcdeafdef"。

输出： 2。

解释：

两个子字符串是 "abcdea" 和 "fdef"。

题目来自力扣3557。

算法分步解析

该算法使用贪心策略和位运算优化来高效解决问题。以下是详细的分步过程：

1. 初始化阶段

• 定义ans变量统计有效子串数量，初始为0。
• 定义seen变量作为位掩码（32位整数），初始为0，用于记录最近出现过的字符（小写字母映射到0-25位）。
• 从索引i = 3开始遍历字符串（因为子串长度至少为4，需检查word[i-3]到word[i]的范围）。

2. 遍历与字符记录

• 对于每个位置i（从第4个字符开始）：
- • 更新位掩码：将word[i-3]对应的位设为1（seen |= 1 << (word[i-3] - 'a')）。这一步记录当前窗口前第3个字符的出现状态。
- • 检查终止条件：判断word[i]是否在seen中出现过（seen >> (word[i] - 'a') & 1 > 0）。若为真，说明存在以word[i]结尾且长度≥4的子串，其首尾字符相同。
  - • 例如，当i=5时，若word[5]与之前某个word[j]（j≤2）相同，则子串word[j:5+1]满足条件。

3. 贪心选择与跳跃

• 一旦检测到有效子串（首尾字符相同）：
- • 计数器ans加1。
- • 重置seen为0，清空历史字符记录。
- • 跳跃指针：将索引i增加3（i += 3），确保下一个子串不会与当前子串重叠。跳跃后，循环本身的i++会使下一次检查从i+4开始，避免重复利用字符。

4. 终止与返回

• 遍历完成后，返回ans作为最大不相交子串数量。
• 示例word = "abcdeafdef"：
- • 检测到"abcdea"（首尾'a'相同）后计数为1，跳过中间字符。
- • 继续检测到"fdef"（首尾'f'相同）后计数为2。

时间与空间复杂度

• 时间复杂度：O(n)。每个字符最多被访问一次（跳跃机制避免重复扫描），位运算和判断操作均为O(1)。
• 空间复杂度：O(1)。仅使用固定大小的变量（ans, seen, i），与输入规模无关。

关键设计思想

• 贪心选择：优先选择最短的有效子串（长度刚好为4时最优），以最大化子串数量。
• 位运算优化：用seen的比特位替代哈希表，快速查询字符出现历史。
• 跳跃式遍历：通过i += 3避免重叠，减少冗余检查。

此算法高效利用了问题约束（字符集小、子串长度固定），实现了线性时间与常数空间的最优解。

Go完整代码如下：

package main

import (
    "fmt"
)

func maxSubstrings(word string) (ans int) {
    seen := 0
    for i := 3; i < len(word); i++ {
        seen |= 1 << (word[i-3] - 'a')
        if seen>>(word[i]-'a')&1 > 0 { // 再次遇到 word[i]
            ans++
            seen = 0
            i += 3
        }
    }
    return
}

func main() {
    word := "abcdeafdef"
    result := maxSubstrings(word)
    fmt.Println(result)
}

Python完整代码如下：

# -*-coding:utf-8-*-

def max_substrings(word: str) -> int:
    ans = 0
    seen = 0
    i = 3
    while i < len(word):
        # 将前3个位置的字符记录到seen中
        seen |= 1 << (ord(word[i - 3]) - ord('a'))
        # 检查当前字符是否在seen中出现过
        if (seen >> (ord(word[i]) - ord('a'))) & 1 > 0:
            ans += 1
            seen = 0
            i += 3  # 跳过3个字符
        i += 1
    return ans

# 测试代码
if __name__ == "__main__":
    word = "abcdeafdef"
    result = max_substrings(word)
    print(result)

C++完整代码如下：

#include <iostream>
#include <string>
using namespace std;

int maxSubstrings(string word) {
    int ans = 0;
    int seen = 0;
    
    for (int i = 3; i < word.length(); i++) {
        seen |= 1 << (word[i - 3] - 'a');
        if ((seen >> (word[i] - 'a')) & 1) { // 再次遇到 word[i]
            ans++;
            seen = 0;
            i += 3;
        }
    }
    
    return ans;
}

int main() {
    string word = "abcdeafdef";
    int result = maxSubstrings(word);
    cout << result << endl;
    return0;
}