java - 最长的字符回文字符串

Question

学校作业中的问题描述最长的回文字符串

我的复杂度为 O(N^2)。如何实现 O(N*log(N))**

我的代码

int maxL = 0;
    for (int i = 0; i < S.length(); i++) {
        String currentString = String.valueOf(S.charAt(i));
        for (int j = i + 1; j < S.length(); j = j + 1) {
            String jStr = String.valueOf(S.charAt(j));
            if (currentString.contains(jStr)) {
                currentString = currentString.replace(jStr, "");
                int len = j - i + 1;
                if (currentString.length() == 0 && maxL < len) {
                    maxL = len;
                }
            } else {
                currentString = currentString + jStr;
            }
        }
    }
    return maxL;

Answer 1

这个问题可以使用 O(n) 空间在 O(n) 时间内解决。以下算法使用位集来跟踪从给定字符串开头开始的子字符串的不平衡字符。它对字符串进行单次传递并记住它已经在 HashMap 中看到的状态。每当我们第二次看到相同的状态时，我们就找到了一个有效的密码:只需从当前子字符串的开头删除旧的较短子字符串即可。

private static int index(char c) {
    if (c < '0') throw new IllegalArgumentException("illegal char");
    if (c <= '9') return c - '0';
    if (c < 'a') throw new IllegalArgumentException("illegal char");
    if (c <= 'z') return c - 'a' + 10;
    throw new IllegalArgumentException("illegal char");
}

private static int solution(String s) {
    HashMap<BitSet, Integer> states = new HashMap<>();
    int longest = 0;
    BitSet state = new BitSet();
    states.put((BitSet) state.clone(), 0);
    for (int i = 0; i < s.length(); i++) {
        char c = s.charAt(i);
        state.flip(index(c));
        Integer seenAt = states.get(state);
        if (seenAt != null) {
            int len = i - seenAt + 1;
            if (len > longest) longest = len;
        } else {
            states.put((BitSet) state.clone(), i + 1);
        }
    }
    return longest;
}