测试用例在执行特殊回文字符串程序时失败

Question

• 我试图解决黑客等级问题，以计算字符串中包含的特殊回文字符串的数量
• 要考虑特殊回文字符串，所有字符都应相同，除中间字符外的所有字符都相同
• 例如，string=asasd，那么回文字符串是{a、s、a、s，d、asa、sas}
• 在这个程序中，两个测试用例分别用字符串asasd和aaaa传递
• 字符串abcbaba
的一个测试用例失败
• 我研究了第二个条件，但我对执行感到震惊
• 你们能用你们的建议帮我解决问题吗
• 提供以下完整代码：

import java.util.Scanner;
import java.io.BufferedReader;
import java.io.InputStreamReader;
public class MyClass {
    public static void main(String args[]) {
        int counter=0;
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt(); // read an integer from input stream.
        String s = scanner.next();
        char string_array[] = s.toCharArray();
        for(int i=0; i<s.length(); i++){
            for(int j=i; j<=s.length(); j++){
                if(i != j){
                    String s1 = s.substring(i,j);
                    String rev = "";
                    for(int z=0; z<s1.length(); z++){
                    rev = rev + s1.charAt(s1.length()-1-z);
                    }
                    //System.out.println("s1=" + s1 +  "rev=" + rev);
                    int count = s1.compareTo(rev);
                    if(count == 0){
                    counter++;
                }
                }
            }

        }
        System.out.println(counter);
}

Answer 1

您的算法没有检查字符相等的特殊回文要求。以下算法添加了这种检查：

public class MyClass {
    public static void main(String args[]) {
        int counter=0;
        String s = "abcbaba";
        char string_array[] = s.toCharArray();
        for(int i=0; i<s.length(); i++){
            for(int j=i; j<=s.length(); j++){
                if(i != j){
                    String s1 = s.substring(i,j);
                    String rev = "";
                    char complianceChar = s1.charAt(0);
                    boolean isSpecialPalindrom = true;
                    boolean isLengthEven = s1.length()%2==0;
                    for(int z=0; z<s1.length(); z++) {
                        char c = s1.charAt(s1.length()-1-z);
                        rev = rev + c;
                        boolean isMiddleChar = (z == (s1.length()-1)/2);
                        if(isSpecialPalindrom && (isLengthEven || !isMiddleChar)) {
                            isSpecialPalindrom = (c == complianceChar);
                        }
                    }
                    int count = s1.compareTo(rev);
                    if(count == 0 && isSpecialPalindrom){
                        System.out.println(rev);
                        counter++;
                    }
                }
            }
        }
        System.out.println(counter);
    }
}

输出是:

a
b
bcb
c
b
bab
a
aba
b
a
10