Hard

题目描述

给你一个只包含小写字母的字符串 s，你需要找到 s 中最多数量的非空子字符串，满足：

  1. 这些字符串之间互不重叠，也就是说，对于任意两个子字符串 s[i..j] 和 s[x..y]，要么 j < x 要么 i > y。
  2. 如果一个子字符串包含字符 c，那么 s 中所有 c 字符都应该在这个子字符串中。

找到满足上述条件的最多数量的子字符串。如果有多个解答有相同的子字符串数目，返回这些解答中字符串总长度最小的一个。可以证明最小总长度解答存在唯一解。

注意，你可以以任意顺序返回最优解的子字符串。

示例 1：

输入：s = "adefaddaccc"
输出：["e","f","ccc"]
解释：下面列出所有满足第二个条件的子字符串：
[
  "adefaddaccc"
  "adefadda",
  "ef",
  "e",
  "f",
  "ccc",
]
如果我们选择第一个字符串，那么我们无法再选择其他字符串，只能得到 1 个字符串。如果我们选择 "adefadda"，剩下子字符串 "ccc" ，我们可以继续选择它，这样共选择了 2 个字符串。同样我们也不应该选择 "ef"，因为它可以被拆分成 2 个子字符串。因此，最优答案是选择 ["e","f","ccc"] ，答案字符串数目为 3 。

示例 2：

输入：s = "abbaccd"
输出：["d","bb","cc"]
解释：注意到解答 ["d","abba","cc"] 答案也是 3 个字符串，但它的总长度更长，所以不是最优解答。

约束条件：

  • 1 <= s.length <= 10^5
  • s 只包含小写英文字母

解题思路

这道题的核心思路是贪心算法结合区间处理：

  1. 构建字符范围：首先遍历字符串，记录每个字符的最左和最右出现位置，这样每个字符都有一个必须包含的区间范围。

  2. 扩展区间：对于每个字符，其有效子字符串必须包含该字符的所有出现位置。如果在这个区间内还有其他字符，我们需要扩展区间以包含那些字符的完整范围。这个过程可能需要多轮扩展，直到区间稳定。

  3. 贪心选择：将所有有效的子字符串按长度排序，优先选择较短的子字符串。这是因为题目要求在子字符串数量相同时，总长度要最小。

  4. 避免重叠：使用贪心策略，一旦选择了一个子字符串，就标记其覆盖的位置，后续选择时跳过已覆盖的区间。

关键观察：如果两个有效子字符串重叠，那么较短的那个一定完全包含在较长的内部，因此我们总是优先选择较短的子字符串。

时间复杂度主要来自于区间扩展和排序过程，空间复杂度用于存储字符位置信息和候选子字符串。

代码实现

class Solution {
public:
    vector<string> maxNumOfSubstrings(string s) {
        int n = s.length();
        vector<int> left(26, -1), right(26, -1);
        
        // 记录每个字符的左右边界
        for (int i = 0; i < n; i++) {
            int c = s[i] - 'a';
            if (left[c] == -1) left[c] = i;
            right[c] = i;
        }
        
        // 构建有效子字符串
        vector<pair<int, string>> candidates;
        for (int i = 0; i < 26; i++) {
            if (left[i] == -1) continue;
            
            int l = left[i], r = right[i];
            bool valid = true;
            
            // 扩展区间直到稳定
            for (int j = l; j <= r; j++) {
                int c = s[j] - 'a';
                if (left[c] < l) {
                    valid = false;
                    break;
                }
                r = max(r, right[c]);
            }
            
            if (valid) {
                candidates.push_back({r - l + 1, s.substr(l, r - l + 1)});
            }
        }
        
        // 按长度排序
        sort(candidates.begin(), candidates.end());
        
        vector<string> result;
        vector<bool> used(n, false);
        
        for (auto& [len, str] : candidates) {
            int start = s.find(str);
            bool canUse = true;
            
            // 检查是否与已选择的重叠
            for (int i = start; i < start + len; i++) {
                if (used[i]) {
                    canUse = false;
                    break;
                }
            }
            
            if (canUse) {
                result.push_back(str);
                for (int i = start; i < start + len; i++) {
                    used[i] = true;
                }
            }
        }
        
        return result;
    }
};

class Solution:
    def maxNumOfSubstrings(self, s: str) -> List[str]:
        n = len(s)
        left, right = [-1] * 26, [-1] * 26
        
        # 记录每个字符的左右边界
        for i, c in enumerate(s):
            idx = ord(c) - ord('a')
            if left[idx] == -1:
                left[idx] = i
            right[idx] = i
        
        # 构建有效子字符串
        candidates = []
        for i in range(26):
            if left[i] == -1:
                continue
                
            l, r = left[i], right[i]
            valid = True
            
            # 扩展区间直到稳定
            j = l
            while j <= r:
                c_idx = ord(s[j]) - ord('a')
                if left[c_idx] < l:
                    valid = False
                    break
                r = max(r, right[c_idx])
                j += 1
            
            if valid:
                substr = s[l:r+1]
                candidates.append((len(substr), substr))
        
        # 按长度排序
        candidates.sort()
        
        result = []
        used = [False] * n
        
        for length, substr in candidates:
            start = s.find(substr)
            can_use = True
            
            # 检查是否与已选择的重叠
            for i in range(start, start + length):
                if used[i]:
                    can_use = False
                    break
            
            if can_use:
                result.append(substr)
                for i in range(start, start + length):
                    used[i] = True
        
        return result

public class Solution {
    public IList<string> MaxNumOfSubstrings(string s) {
        int n = s.Length;
        int[] left = new int[26];
        int[] right = new int[26];
        Array.Fill(left, -1);
        Array.Fill(right, -1);
        
        // 记录每个字符的左右边界
        for (int i = 0; i < n; i++) {
            int c = s[i] - 'a';
            if (left[c] == -1) left[c] = i;
            right[c] = i;
        }
        
        // 构建有效子字符串
        List<(int length, string str)> candidates = new List<(int, string)>();
        for (int i = 0; i < 26; i++) {
            if (left[i] == -1) continue;
            
            int l = left[i], r = right[i];
            bool valid = true;
            
            // 扩展区间直到稳定
            for (int j = l; j <= r; j++) {
                int c = s[j] - 'a';
                if (left[c] < l) {
                    valid = false;
                    break;
                }
                r = Math.Max(r, right[c]);
            }
            
            if (valid) {
                string substr = s.Substring(l, r - l + 1);
                candidates.Add((substr.Length, substr));
            }
        }
        
        // 按长度排序
        candidates.Sort((a, b) => a.length.CompareTo(b.length));
        
        List<string> result = new List<string>();
        bool[] used = new bool[n];
        
        foreach (var (length, str) in candidates) {
            int start = s.IndexOf(str);
            bool canUse = true;
            
            // 检查是否与已选择的重叠
            for (int i = start; i < start + length; i++) {
                if (used[i]) {
                    canUse = false;
                    break;
                }
            }
            
            if (canUse) {
                result.Add(str);
                for (int i = start; i < start + length; i++) {
                    used[i] = true;
                }
            }
        }
        
        return result;
    }
}

var maxNumOfSubstrings = function(s) {
    const n = s.length;
    const left = new Array(26).fill(-1);
    const right = new Array(26).fill(-1);
    
    // 记录每个字符的左右边界
    for (let i = 0; i < n; i++) {
        const c = s.charCodeAt(i) - 97;
        if (left[c]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

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

其中 n 是字符串长度，k 是字符种类数（最多26）。时间复杂度中，O(n) 用于遍历字符串，O(k²) 用于构建和验证候选子字符串（每个字符最多扩展 k 次）。空间复杂度包括存储字符位置信息和标记数组。

相关题目