如何使用 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); 应该 return 3 因为有效的子字符串是： "cabc" , "cabc" , "cabcabc"

这是我的代码，但它没有 return 正确答案：

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

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

How to find numbers of valid subString using O(n) time complexity algorithm

java

algorithm

complexity-theory

substring

time-complexity