具有唯一字母的子串数

Question

我有一个字符串，现在想计算子字符串的最小数量，以便子字符串中的字母应该只出现一次。

例子：

Input : cycle
Output : 2

解释：

Possible substrings are : ('cy', 'cle') or ('c', 'ycle')

例子：

Input : aaaa
Output : 4

解释：

Possible substrings are : ('a', 'a', 'a', 'a')

我能够获得所有可能的子字符串，但我无法理解如何实现此任务的解决方案：

static int distinctSubString(String S) {
    int count = 0;
    int n = S.length();
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j <= n; j++) {
            String s = S.substring(i, j);
            System.out.println(s);
        }
    }
    return count;
}

Answer 1

您应该注意，这可以贪婪地完成。每当你遇到一个角色时，它可以被添加到之前的分区中，也可以开始一个新的分区。如果两者都可能，那么您始终可以添加到前一个分区而不更改任何其他内容，因此答案不会因此变得更糟。因此，解决方案是跨字符运行，并在可以时向分区添加一个。该解是渐近最优的。请注意，如果您的字符落入特定范围内，则使用数组而不是 HashSet 可以显着提高性能。

static int distinctSubString(String S) {
    int count = (S.isEmpty()) ? 0 : 1;
    S = S.toLowerCase();
    HashSet<Character> letters = new HashSet<Character>();
    for (int i = 0; i < S.length(); i++) {
        if (letters.contains(S.charAt(i))) {
            letters.clear();
            count++;
        }
        letters.add(S.charAt(i));
    }
    return count;
}