取得包含最長反轉字串的子字串演算法實作

本文提供一個 Java 類別 StringX，實作從指定字串中找出「存在反轉字串的最大長度子字串」的功能。若有多個符合條件的子字串，則回傳最右側的一個。

核心邏輯

程式包含三個主要方法：

• getMaxLenReverseString(String str)：主入口，遞增檢查可能的反轉字串長度，呼叫輔助方法尋找位置。
• getPosOfReverseString(String str, int lenOfReverseStr)：從右向左掃描，尋找指定長度且其反轉字串也存在於原字串中的子字串起始位置。
• getReverseString(String str, int s, int len)：根據起始索引與長度，取得子字串的反轉字串。

程式碼範例

public class StringX {
    public String getMaxLenReverseString(String str) {
        int startIndex = -1;
        int lenOfReverseStr = 2;
        int tmp = -1;
        for (int i = lenOfReverseStr; i <= str.length(); i++) {
            tmp = getPosOfReverseString(str, i);
            if (tmp != -1) {
                lenOfReverseStr = i;
                startIndex = tmp;
                str = str.substring(0, tmp + lenOfReverseStr);
            } else {
                break;
            }
        }
        return startIndex == -1 ? str.substring(0,1) : str.substring(startIndex, startIndex + lenOfReverseStr);
    }

    public int getPosOfReverseString(String str, int lenOfReverseStr) {
        if (lenOfReverseStr > str.length() || lenOfReverseStr < 1) return -1;
        for (int i = str.length() - lenOfReverseStr; i >= 0; i--) {
            if (str.indexOf(getReverseString(str, i, lenOfReverseStr)) != -1) return i;
        }
        return -1;
    }

    public String getReverseString(String str, int s, int len) {
        int tmp = s + len;
        if (tmp > str.length() || tmp < 1 || s * len < 0) return "";
        StringBuilder reverseStr = new StringBuilder(len);
        for (int i = s + len - 1; i >= s; i--) reverseStr.append(str.charAt(i));
        return reverseStr.toString();
    }

    public static void main(String[] args) {
        StringX objTest = new StringX();
        System.out.println(objTest.getMaxLenReverseString("ARSTUVYWFDEVUTSRZ"));
        System.out.println(objTest.getMaxLenReverseString("ABC"));
        System.out.println(objTest.getMaxLenReverseString("DEFDEDJH"));
        System.out.println(objTest.getMaxLenReverseString("HIJKLKJIH"));
    }
}

執行結果說明

主程式測試四組字串，分別輸出符合條件的最長反轉子字串。演算法採用從短到長嘗試長度、從右向左搜尋位置的策略，確保回傳最右側的最大長度解。