java - 如何使用 O(n) 时间复杂度算法查找有效子字符串的数量

Question

所以我需要一个java方法来接收一个String类型变量，一个char类型变量和一个int类型变量:

public static int subStrMaxC(String s, char c, int k)

所以这个方法的思想是检查 String 中有多少个子字符串以字符 c 开头和结尾，并且其中最多有 k c 个字符。同时使用 O(n) 的时间复杂度 while n == s.length()添加以下 API 文档:

/**
     * Checks how many Sub-Strings are within a given String that starts and ends with a given character and also has that character inside the Sub-String maximum a given amount of times.
     * @param s the String to check for the Sub-String within.
     * @param c the character to check the Sub-String according to.
     * @param k the amount of time that the given character has to be within every Sub-String.
     * @return the number of the valid Sub-Strings.
     * @timeComplexity O(n) n - the String's (s) length.
     * @SpaceComplexity O(1)
     */

例如: subStrMaxC("abcabcabc", 'c', 1);应该返回 3 因为有效的子字符串是:"cabc", "cabc", "cabcabc"

这是我的代码，但它没有返回正确的答案:

public static int subStrMaxC(String s, char c, int k) {
    int count = 0, toReturn = 0;
    for(int index = 0; index < s.length(); index++) {
        if(s.charAt(index) == c)
            count++;
    }

    while(k >= 0) {
        if(k == 0)
            return toReturn;
        else if(k % 2 == 0) {
            toReturn += count - (k + 1) - toReturn;
            k--;
        }
        else {
            toReturn += count / 2 - toReturn;
            k--;
        }
    }
    return toReturn;
}

很想得到一些帮助!谢谢!

Answer 1

我们需要做一些观察来解决这个问题:

假设我们有以索引 ith 结尾的最长有效子串，其中包含 x字符 c , 与 x <= k ，因此，它总共包含 x + 2字符 c .我们可以说，任何以此索引结尾的子串 ith并从第一个 x+1 中的任何一个开始字符是一个有效的子字符串。

因此，对于每个字符 c在字符串中，我们只需要找到字符数c (表示为 count )站在它前面，如果它大于 k + 1 , 只需添加 k + 1结果，否则，只需添加 count .

伪代码如下:

int result = 0;
int count = 0;
for(int i = 0; i < s.length(); i++){
    if(s.charAt(i) == c){
       result += Integer.min(k + 1, count);
       count++;
    } 
}

时间复杂度:O(n)

工作演示:https://ideone.com/aUpxk5