Medium

题目描述

给你一个字符串 word。

返回 word 中最多有多少个不相交的子串，这些子串至少有四个字符长，并且开头和结尾是相同的字母。

示例 1：

输入：word = "abcdeafdef"
输出：2
解释：
两个子串是 "abcdea" 和 "fdef"。

示例 2：

输入：word = "bcdaaaab"
输出：1
解释：
唯一的子串是 "aaaa"。注意我们不能同时选择 "bcdaaaab"，因为它与另一个子串相交。

约束条件：

  • 1 <= word.length <= 2 * 10^5
  • word 只包含小写英文字母。

提示：

  • 可以使用动态规划来解决这个问题吗？
  • 对于每个字符 c，按顺序存储所有出现的索引
  • 在每个位置 i，设 j 为 word[i] 的第一个索引；如果 i - j >= 3，我们可以形成子串 [j, i]
  • 对于每个索引，还要存储在该索引之前结束的任何子串的最大值

解题思路

这是一个经典的动态规划问题，需要找到最多的不相交子串。

核心思路：

  1. 使用动态规划，dp[i] 表示考虑到位置 i 时能获得的最大子串数量
  2. 对于每个字符，记录它第一次出现的位置
  3. 当遍历到位置 i 时，如果当前字符之前出现过，且距离足够长（≥4），就可以形成一个有效子串
  4. 选择是否采用这个新子串：要么延续之前的最优解，要么采用新子串加上该子串开始位置之前的最优解

算法步骤：

  1. 初始化哈希表记录每个字符的首次出现位置
  2. 初始化 dp 数组，dp[i] 表示到位置 i 的最大子串数
  3. 遍历字符串：
    • 如果当前字符未出现过，记录位置
    • 如果已出现过且距离≥4，可以形成子串，更新 dp[i]
    • 更新字符的首次出现位置为当前位置（贪心策略）
  4. 返回 dp[n-1]

贪心优化： 当找到一个有效子串时，立即更新该字符的起始位置，这样可以最大化后续可能的子串数量。

代码实现

class Solution {
public:
    int maxSubstrings(string word) {
        int n = word.length();
        vector<int> dp(n, 0);
        unordered_map<char, int> firstPos;
        
        for (int i = 0; i < n; i++) {
            char c = word[i];
            
            // 继承前一个位置的最优解
            if (i > 0) {
                dp[i] = dp[i - 1];
            }
            
            // 检查是否可以形成新的子串
            if (firstPos.count(c) && i - firstPos[c] >= 3) {
                int start = firstPos[c];
                int prevMax = (start > 0) ? dp[start - 1] : 0;
                dp[i] = max(dp[i], prevMax + 1);
                firstPos[c] = i; // 贪心更新起始位置
            } else if (!firstPos.count(c)) {
                firstPos[c] = i; // 第一次出现
            }
        }
        
        return dp[n - 1];
    }
};

class Solution:
    def maxSubstrings(self, word: str) -> int:
        n = len(word)
        dp = [0] * n
        first_pos = {}
        
        for i in range(n):
            c = word[i]
            
            # 继承前一个位置的最优解
            if i > 0:
                dp[i] = dp[i - 1]
            
            # 检查是否可以形成新的子串
            if c in first_pos and i - first_pos[c] >= 3:
                start = first_pos[c]
                prev_max = dp[start - 1] if start > 0 else 0
                dp[i] = max(dp[i], prev_max + 1)
                first_pos[c] = i  # 贪心更新起始位置
            elif c not in first_pos:
                first_pos[c] = i  # 第一次出现
        
        return dp[n - 1]

public class Solution {
    public int MaxSubstrings(string word) {
        int n = word.Length;
        int[] dp = new int[n];
        Dictionary<char, int> firstPos = new Dictionary<char, int>();
        
        for (int i = 0; i < n; i++) {
            char c = word[i];
            
            // 继承前一个位置的最优解
            if (i > 0) {
                dp[i] = dp[i - 1];
            }
            
            // 检查是否可以形成新的子串
            if (firstPos.ContainsKey(c) && i - firstPos[c] >= 3) {
                int start = firstPos[c];
                int prevMax = (start > 0) ? dp[start - 1] : 0;
                dp[i] = Math.Max(dp[i], prevMax + 1);
                firstPos[c] = i; // 贪心更新起始位置
            } else if (!firstPos.ContainsKey(c)) {
                firstPos[c] = i; // 第一次出现
            }
        }
        
        return dp[n - 1];
    }
}

/**
 * @param {string} word
 * @return {number}
 */
var maxSubstrings = function(word) {
    const n = word.length;
    const dp = new Array(n).fill(0);
    const firstPos = new Map();
    
    for (let i = 0; i < n; i++) {
        const c = word[i];
        
        // 继承前一个位置的最优解
        if (i > 0) {
            dp[i] = dp[i - 1];
        }
        
        // 检查是否可以形成新的子串
        if (firstPos.has(c) && i - firstPos.get(c) >= 3) {
            const start = firstPos.get(c);
            const prevMax = (start > 0) ? dp[start - 1] : 0;
            dp[i] = Math.max(dp[i], prevMax + 1);
            firstPos.set(c, i); // 贪心更新起始位置
        } else if (!firstPos.has(c)) {
            firstPos.set(c, i); // 第一次出现
        }
    }
    
    return dp[n - 1];
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值
时间复杂度O(n)
空间复杂度O(n + k)

其中 n 是字符串长度，k 是不同字符的数量（最多 26）。时间复杂度为线性，因为每个位置只遍历一次。空间复杂度包括 dp 数组的 O(n) 和哈希表的 O(k)。