每个字符个数为k的子串个数

Question

资料来源：https ://www.geeksforgeeks.org/number-substrings-count-character-k/

给定一个字符串和一个整数 k，找出所有不同字符恰好出现 k 次的子字符串的数量。

使用两个指针/滑动窗口方法寻找 O(n) 的解决方案。我只能找到满足此条件的最长子字符串，但不能找到该长子字符串中的子字符串。

例如：abababa，k = 2
我的解决方案找到 abab、ababba 等，但在 ababba 中找不到 bb。

有人可以帮我理清逻辑吗？

Answer 1

如果您可以编辑您的问题以包含您的解决方案代码，我很乐意为您提供帮助。

现在我正在分享我的解决方案代码（在java中），它在 O(n ² )中运行。我添加了足够的注释以使代码不言自明。尽管如此，解决方案的逻辑如下：

正如您正确指出的那样，可以使用滑动窗口方法（具有可变窗口大小）来解决该问题。下面的解决方案考虑了所有可能的子字符串，使用嵌套的 for 循环来设置开始和结束索引。对于每个子字符串，我们检查子字符串中的每个元素是否恰好出现 k 次。

为了避免重新计算每个子字符串的计数，我们在映射中维护计数，并在增加结束索引（滑动窗口）时不断将新元素放入映射中。这确保了我们的解决方案运行时间为 O(n ² ) 而不是 O(n ³ )。

为了进一步提高效率，如果子字符串的大小符合我们的要求，我们只检查单个元素的数量。例如，对于 n 个唯一元素（映射中的键），所需子字符串的大小将为 n*k。如果子字符串的大小与该值不匹配，则无需检查单个字符出现的次数。

import java.util.*;

/**
 * Java program to count the number of perfect substrings in a given string. A
 * substring is considered perfect if all the elements within the substring
 * occur exactly k number of times.
 * 
 * @author Codextor
 */

public class PerfectSubstring {

    public static void main(String[] args) {
        String s = "aabbcc";
        int k = 2;
        System.out.println(perfectSubstring(s, k));

        s = "aabccc";
        k = 2;
        System.out.println(perfectSubstring(s, k));
    }

    /**
     * Returns the number of perfect substrings in the given string for the
     * specified value of k
     * 
     * @param s The string to check for perfect substrings
     * @param k The number of times every element should occur within the substring
     * @return int The number of perfect substrings
     */
    public static int perfectSubstring(String s, int k) {

        int finalCount = 0;

        /*
         * Set the initial starting index for the subarray as 0, and increment it with
         * every iteration, till the last index of the string is reached.
         */
        for (int start = 0; start < s.length(); start++) {

            /*
             * Use a HashMap to store the count of every character in the subarray. We'll
             * start with an empty map everytime we update the starting index
             */
            Map<Character, Integer> frequencyMap = new HashMap<>();

            /*
             * Set the initial ending index for the subarray equal to the starting index and
             * increment it with every iteration, till the last index of the string is
             * reached.
             */
            for (int end = start; end < s.length(); end++) {
                /*
                 * Get the count of the character at end index and increase it by 1. If the
                 * character is not present in the map, use 0 as the default count
                 */
                char c = s.charAt(end);
                int count = frequencyMap.getOrDefault(c, 0);
                frequencyMap.put(c, count + 1);

                /*
                 * Check if the length of the subarray equals the desired length. The desired
                 * length is the number of unique characters we've seen so far (size of the map)
                 * multilied by k (the number of times each character should occur). If the
                 * length is as per requiremets, check if each element occurs exactly k times
                 */
                if (frequencyMap.size() * k == (end - start + 1)) {
                    if (check(frequencyMap, k)) {
                        finalCount++;
                    }
                }
            }
        }
        return finalCount;
    }

    /**
     * Returns true if every value in the map is equal to k
     * 
     * @param map The map whose values are to be checked
     * @param k   The required value for keys in the map
     * @return true if every value in the map is equal to k
     */
    public static boolean check(Map<Character, Integer> map, int k) {
        /*
         * Iterate through all the values (frequency of each character), comparing them
         * with k
         */
        for (Integer i : map.values()) {
            if (i != k) {
                return false;
            }
        }
        return true;
    }
}