Medium

题目描述

给你一个由小写英文字母组成的字符串 s。

返回一个整数，表示你可以将 s 分割成的最大子串数，使得每个子串都以不同的字符开头（即没有两个子串以相同的字符开头）。

示例 1：

输入：s = "abab"
输出：2
解释：
将 "abab" 分割为 "a" 和 "bab"。
每个子串都以不同的字符开头，即 'a' 和 'b'。因此，答案是 2。

示例 2：

输入：s = "abcd"
输出：4
解释：
将 "abcd" 分割为 "a"、"b"、"c" 和 "d"。
每个子串都以不同的字符开头。因此，答案是 4。

示例 3：

输入：s = "aaaa"
输出：1
解释：
"aaaa" 中的所有字符都是 'a'。
只有一个子串可以以 'a' 开头。因此，答案是 1。

约束条件：

  • 1 <= s.length <= 10^5
  • s 由小写英文字母组成。

提示：

  • 统计 s 中不同字符的数量

解题思路

这道题的核心思想非常直观：由于每个子串必须以不同的字符开头，所以最多只能有和字符串中不同字符数量相等的子串。

分析过程：

  1. 关键观察：如果字符串中只有 k 个不同的字符，那么最多只能分割出 k 个子串，因为每个子串的开头字符必须不同。

  2. 贪心策略：为了最大化子串数量，我们应该让每个不同的字符都有机会作为某个子串的开头。这样可以确保达到理论上的最大值。

  3. 实现方法：

    • 使用哈希集合统计字符串中所有不同字符的数量
    • 由于题目限制字符串只包含小写英文字母，也可以用布尔数组优化空间

  4. 正确性证明：

    • 如果有 k 个不同字符，我们总是可以构造出 k 个子串：让每个不同字符都作为一个子串的开头
    • 不可能有超过 k 个子串，因为开头字符必须不同

这种解法的优势在于时间复杂度仅为 O(n)，空间复杂度为 O(1)（使用数组）或 O(k)（使用哈希集合，k 最多为26）。

代码实现

class Solution {
public:
    int maxDistinct(string s) {
        bool seen[26] = {false};
        int count = 0;
        
        for (char c : s) {
            if (!seen[c - 'a']) {
                seen[c - 'a'] = true;
                count++;
            }
        }
        
        return count;
    }
};

class Solution:
    def maxDistinct(self, s: str) -> int:
        return len(set(s))

public class Solution {
    public int MaxDistinct(string s) {
        bool[] seen = new bool[26];
        int count = 0;
        
        foreach (char c in s) {
            if (!seen[c - 'a']) {
                seen[c - 'a'] = true;
                count++;
            }
        }
        
        return count;
    }
}

var maxDistinct = function(s) {
    const seen = new Set();
    
    for (let c of s) {
        seen.add(c);
    }
    
    return seen.size;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度大O表示法
时间复杂度O(n)
空间复杂度O(1)

其中 n 是字符串的长度。由于字符集大小固定为26个小写字母，空间复杂度为常数级别。