寻找具有相同字符的连续字符串的最大长度

Question

我正在解这个问题来自代码强制。，我有一个复杂度为O(n平方)的解。但是，在某些测试用例上，时间限制超过了。问题是：

高中生Vasya得到了一串长n的生日礼物。这个字符串仅由字母'a‘和'b’组成。Vasya表示字符串的美，它是由等号组成的子字符串(连续子序列)的最大长度。Vasya只能更改原始字符串的k个字符。他所能达到的最大美是什么？输入输入的第一行包含两个整数n和k (1 ≤ n ≤ 100 000， 0 ≤ k ≤ n) --字符串的长度和要更改的最大字符数。第二行包含字符串，只包含字母'a‘和'b’。输出打印唯一的整数--字符串Vasya的最大美可以通过更改不超过k个字符来实现。示例输入/输出示例:8 1 aabaabaa输出5

我的解决办法是：

import java.util.Scanner;
public class CF676C {
public static void main(String args[]){
    Scanner in = new Scanner(System.in);
    int n = in.nextInt(), max = in.nextInt(),a=0,b=0;

    String s = in.next();
    int i,j;
    for(i=0;i<n;i++){
        if(s.charAt(i) == 'a'){
            ++a;
        }
        else{
            ++b;
        }
    }
    char z;
    if(a<=b){
        z='a';
    }
    else{
        z='b';
    }
    int max1;
    int count=0;
    int temp=0;
    for(i=0;i<s.length();i++)
    {
        max1=max;
        count=0;
        for(j=i;j<s.length()&&max1!=-1;j++)
        {
            if(s.charAt(j)==z&&max1!=-1)
            {
                max1--;
            }
            if(max1!=-1)
            {
                count++;
            }
        }
        if(count>temp)
        {
            temp=count;
        }
    }
    System.out.println(temp);
}
}

我不明白如何减少代码占用的时间。有没有其他可用的解决方案或方法？

Answer 1

是的，您可以更快地解决这个问题，使用一个O(n)算法，使用一个左指针和一个右指针来分隔子字符串。

对于输入字符串中的每个字符，其思想是保持数组在给定的'a'指针之间计数left和'b'的数量，这将表示子字符串的开始和当前字符。

当每个'a'或每个'b'的计数小于允许更改的字符数时，我们可以考虑进行更改并递增答案。然后，当这两个计数都大于允许更改的字符数时，这意味着我们不能更改更多的字符，因此我们达到了最大长度：left指针增加了，该指针处的字符计数减少了。

'a'和'b'字符的计数可以建模为整数数组(索引0对应于'a'的计数，而索引1对应于'b'的计数)。

Scanner in = new Scanner(System.in);
int n = in.nextInt(), max = in.nextInt();
String s = in.next();

int left = 0, answer = 0;
int[] count = { 0, 0 };
for (char c : s.toCharArray()) {
    count[c - 'a']++;
    if (Math.min(count[0], count[1]) > max) {
        count[s.charAt(left) - 'a']--;
        left++;
    } else {
        answer++;
    }
}
System.out.println(answer);

这种方法通过了所有挑战的测试。

Answer 2

目前，整个解决方案都在您的main方法中。在OOP中，您的main方法通常应该保留为仅作为程序的入口点，而不是整个程序的入口点。这有助于使代码更好地组织起来，更容易理解和维护。

在这种情况下，我会将实际解决问题的代码移到另一个类中，以帮助使其更通用，只需读取输入并在main中打印输出即可。

有几个突出的命名问题。首先，问题说明输入数字是n和k，它们通常用于数学表示法，作为惯例；然而，这些数字不一定能很好地转换成代码，因为代码最好是以这样一种方式来编写，这样才能清楚地表明意图。

首先，我将更改输入变量名如下：

• n到strLength
• max (或，问题中的k )到maxCharChangesAllowed
• s ( As和Bs的输入字符串)到targetStr (或类似的东西)

将它们移动到新类中的静态方法签名如下所示：

class CodeForce676C {
    public static int solve(int strLength, int maxCharChangesAllowed, String targetStr) {
        // ...
    }
}

同样的，a，b也不是很清楚，我建议countOfA和countOfB。我们也将把这个逻辑提取到一个单独的方法中。我们可以消除您的char z，直接从方法返回结果。我们还可以通过使用三元算子而不是if-then-else结构来简化返回。

我们还可以利用字符串长度作为输入的事实，并为自己节省String.length()计算。

请注意，不建议在循环签名之外声明int i, j迭代计数器，除非您将这些变量用于除循环本身之外的其他内容(而不是)。编译器将知道在循环退出后不需要i，因此它可以删除它，如果在同样使用i的方法中有另一个循环，那么它只会创建一个新的循环。

private static char findCharWithLeastFrequency(String targetStr, int strLength) {
    int countOfA = 0;
    int countOfB = 0;
    for (int i = 0; i < strLength; i++) {
        targetStr.charAt(i) == 'a' ? ++countOfA : ++countOfB;
        if (targetStr.charAt(i) == 'a') {
            ++countOfA;
        } else {
            ++countOfB;
        }
    }
    return countOfA <= countOfB ? 'a' : 'b';
}

同样，我们也可以将逻辑的另一部分(使用max1和count)移动到自己的方法中。我把max1改名为changesRemaining，count改名为charCount，temp改名为substringLength。算法本身已经在图纳基的回答中得到了解决，所以我只是简单地修改了现有的算法，以使代码更容易理解和更简洁。

这是一个在repl.it上的工作演示。要运行给定的测试用例，请运行它并输入控制台：8 1 aabaabaa

import java.util.Scanner;

class Main {
    public static void main(String args[]) {
        Scanner in = new Scanner(System.in);
        // Read the values from the input
        int n = in.nextInt();
        int k = in.nextInt(); 
        String s = in.next();
        // Solve the calculation and print the result to console:
        System.out.println(CodeForce676C.solve(n, k, s));
    }
}

class CodeForce676C {

    public static int solve(int strLength, int maxCharChangesAllowed, String targetStr) {
        char leastFrequentChar = findCharWithLeastFrequency(targetStr, strLength);
        return getLengthOfLongestPossibleSubstring(
                targetStr, 
                maxCharChangesAllowed, 
                leastFrequentChar, 
                strLength);
    }

    private static char findCharWithLeastFrequency(String targetStr, int strLength) {
        int countOfA = 0;
        int countOfB = 0;
        for (int i = 0; i < strLength; i++) {
            if (targetStr.charAt(i) == 'a') {
                ++countOfA;
            } else {
                ++countOfB;
            }
        }
        return countOfA <= countOfB ? 'a' : 'b';
    }

    private static int getLengthOfLongestPossibleSubstring(
            String targetStr, 
            int maxCharChangesAllowed, 
            char leastFrequentChar,
            int strLength) {
        int changesRemaining;
        int charCount = 0;
        int substringLength = 0;
        for (int i = 0; i < strLength; i++) {
            // Reset values on each outer iteration
            changesRemaining = maxCharChangesAllowed;
            charCount = 0;
            for (int j = i; j < strLength && changesRemaining != -1; j++) {
                if (targetStr.charAt(j) == leastFrequentChar && changesRemaining != -1) {
                    changesRemaining--;
                }
                if (changesRemaining != -1) {
                    charCount++;
                }
            }
            if(charCount > substringLength) {
                substringLength = charCount;
            }
        }
        return substringLength;
    }
}