java - 使字符串连续所需的最少更改 x 数量A 的之后，然后是 (n-x) 个 B 的之后

Question

我陷入了 Java 中与问题相关的字符串之一。我的逻辑对于某些测试用例来说效果很好，但不适用于所有测试用例。请建议我以下问题的实际逻辑::

给我一​​个包含 n 个字符的字符串 s ，仅包含 A 和 B 。我可以选择任何索引 i 并将 s(i) 更改为 A 或 B。找到最小编号。您必须对字符串 S 进行更改，以使结果字符串的格式为:AAAAA.....BBBBB。换句话说，我的任务是确定最小数量。使得字符串 s 有 x 的变化。开头的 A 个，后面是剩余的 (n-x) 个。 B 的。

示例输入如下 4 3 AAB 5 亚巴巴 1 乙 4 巴巴

第一行:一个整数，表示测试用例的数量 对于每个测试用例: 第一行包含一个整数，表示字符串的大小 第二行包含字符串

我的代码如下

import java.util.*;
class TestClass {
    public static void main(String args[] ) throws Exception {
        Scanner s = new Scanner(System.in);
        TestClass t = new TestClass();
        int test_case = s.nextInt();
        for(int i = 0; i < test_case; i++){
            int len = s.nextInt();
            String none = s.nextLine();
            String str = s.nextLine();
            int cnta = t.count_ab(str,'A');
            int cntb = t.count_ab(str,'B');
            char c1 = '1';
            if(cnta > cntb){
                c1 = 'A';
            }
            else{
                c1 = 'B';
            }
            int count = 0;
            int c1_count = 0;
            int c2_count = 0;
            if(str.length() > 1){
                String rev = "";
                c1_count = t.cnt_init_a(str, 'A');
                StringBuilder sb = new StringBuilder(str);
                rev = sb.reverse().toString();
                c2_count = t.cnt_init_a(rev, 'B');
                int rem_len = str.length() - c2_count;
                for(int h = c1_count; h < rem_len; h++){
                    if(Character.compare(str.charAt(h), c1) != 0){
                        count = count + 1;
                    }
                }

            }
            System.out.println(count);
        }
    }

    public int cnt_init_a(String str, char c){
        int cnt = 0;
        for(int l = 0; l < str.length(); l++){
            if(Character.compare(str.charAt(l), c) == 0){
                cnt = cnt + 1;
            }
            else{
                break;
            }
        }
        return cnt;
    }

    public int count_ab(String str, char c){
        int cnt = 0;
        for(int g = 0; g < str.length(); g++){
            if(Character.compare(str.charAt(g), c) == 0){
                cnt = cnt + 1;
            }
        }
        return cnt;
    }

Answer 1

你的逻辑失败了，例如“BAAAAAAAAAABBBBBBBBBBBB”和“AAAAAAAAAABBBBBBBBBBA”。

您应该首先忽略所有前导 A 和所有尾随 B，因为它们永远不应该更改。

"BAAAAAAAAAABBBBBBBBBB" -> "BAAAAAAAAAA"(删除了尾随的 B)
“AAAAAAAAAABBBBBBBBBBA” -> “BBBBBBBBBBBA”(删除了前导 A)

然后将前导 B 更改为 A，或将尾随 A 更改为 B，以较短者为准。

然后重复该过程。