Java самый длинный палиндром не работает

Учтите, что есть две разные самые длинные подпоследовательности палиндрома (аванава и Avabava), вы можете найти все подпоследовательности итеративно, а затем проверить, являются ли они палиндромом. Я использую карту для сохранения всех подпоследовательностей палиндрома и их длины, а затем просматриваю карту, чтобы выбрать самую длинную. Это решение занимает только первое самое длинное ((аванава):

import java.util.HashMap;
import java.util.Map;

public class Palindrome {
    // set to store all the subsequences
    static Map<String, Integer> subsequences = new HashMap<>();


    public static void main(String[] args) {
        subsequence("havanbava");

        //storing the higher key/value
        Map.Entry<String, Integer> maxEntry = null;

        for (Map.Entry<String, Integer> entry : subsequences.entrySet())
        {
            if (maxEntry == null || entry.getValue().compareTo(maxEntry.getValue()) > 0)
            {
                maxEntry = entry;
            }
        }

        System.out.println(maxEntry.getKey());

    }

    static boolean isPalindrome(String str) {
         int n = str.length();
          for (int i = 0; i < (n/2); ++i) {
             if (str.charAt(i) != str.charAt(n - i - 1)) {
                 return false;
             }
          }

          return true;
    }


    static void subsequence(String str)
    {
        for (int i = 0; i < str.length(); i++) {


            for (int j = str.length(); j > i; j--) {
                String sub_str = str.substring(i, j);

                if (!subsequences.containsKey(sub_str)
                        && isPalindrome(sub_str))
                    subsequences.put(sub_str,sub_str.length());

                for (int k = 1; k < sub_str.length() - 1; k++) {
                    StringBuffer sb = new StringBuffer(sub_str);

                    sb.deleteCharAt(k);

                    subsequence(sb.toString());
                }
            }
        }
    }

}

Учтите также, что итеративное решение требует значительных ресурсов, поэтому для длинных строк оно требует значительных улучшений.

Это возможное решение, если вы хотите, чтобы все были самыми длинными подпоследовательностями (одинаковой длины):

import java.util.HashMap;
import java.util.Map;

public class Palindrome {
    // set to store all the subsequences
    static Map<String, Integer> subsequences = new HashMap<>();


    public static void main(String[] args) {
        subsequence("havanbava");

        //storing the higher key/value
        Map<String, Integer> maxEntries = new HashMap<String, Integer>();

        for (Map.Entry<String, Integer> entry : subsequences.entrySet())
        {
            if (maxEntries.isEmpty()){
                maxEntries.put(entry.getKey(),entry.getValue());
            }else if (entry.getValue().compareTo( maxEntries.entrySet().iterator().next().getValue() ) == 0)
            {
                maxEntries.put(entry.getKey(),entry.getValue());
            }else if ( entry.getValue().compareTo(maxEntries.entrySet().iterator().next().getValue()) > 0){
                maxEntries.clear();
                maxEntries.put(entry.getKey(),entry.getValue());
            }
        }
        for (Map.Entry<String, Integer> maxEntry : maxEntries.entrySet())
            System.out.println(maxEntry.getKey());

    }

    static boolean isPalindrome(String str) {
         int n = str.length();
          for (int i = 0; i < (n/2); ++i) {
             if (str.charAt(i) != str.charAt(n - i - 1)) {
                 return false;
             }
          }

          return true;
    }


    static void subsequence(String str)
    {
        for (int i = 0; i < str.length(); i++) {


            for (int j = str.length(); j > i; j--) {
                String sub_str = str.substring(i, j);

                if (!subsequences.containsKey(sub_str)
                        && isPalindrome(sub_str))
                    subsequences.put(sub_str,sub_str.length());

                for (int k = 1; k < sub_str.length() - 1; k++) {
                    StringBuffer sb = new StringBuffer(sub_str);

                    sb.deleteCharAt(k);

                    subsequence(sb.toString());
                }
            }
        }
    }

}

Это типичная проблема динамическое программирование. Вы можете найти длину самая длинная подпоследовательность палиндрома (LPS) во времени O(n^2). Вы должны построить матрицу мемоизации следующим образом:

     0 1 2 3 4 5 6 7 8 -> indexes
     h a v a n b a v a -> input string
0 h  1 1 1 3 3 3 3 5 7 -> max_len = 7 -> a v a b a v a
1 a  0 1 1 3 3 3 3 5 7 
2 v  0 0 1 1 1 1 3 5 5 
3 a  0 0 0 1 1 1 3 3 3 
4 n  0 0 0 0 1 1 1 1 3 
5 b  0 0 0 0 0 1 1 1 3 
6 a  0 0 0 0 0 0 1 1 3 
7 v  0 0 0 0 0 0 0 1 1 
8 a  0 0 0 0 0 0 0 0 1 

Идея состоит в том, чтобы построить такую ​​матрицу, чтобы matrix[i][j] (0 <= i, j <= len) был равен LPS от i-го индекса до j-го индекса входа.

Если LPS между i-м и j-м индексом (i<=j) имеет длину LPS(i, j), то L:

• Для L=1 имеем: LPS(0,0) = LPS(1,1) = ... = LPS(8,8) = 1
• Для L=2: LPS(0,1) = LPS(1,2) = ... = LPS(7,8) = 1 (если input[i]=input[i+1], LPS(i,i+1)=2, то есть aa или bb, но у нас такого корпуса нет)
• Для L=3 имеем:
  • LPS(0,2) = max(LPS(0,1), LPS(1,2)) = max(1, 1) = 1
  • LPS(1,3) = LPS(1,1) + 2 = 3
  • ...

Еще примеры:

LPS(0,4) = max(LPS(0,3), LPS(1,4))=max(3,2) = 3
LPS(2,7) = LPS(3,6) + 2 = 3 + 2 = 5

Итак, правило:

if input[i] != input[j]
    LPS(i,j) = max(LPS(i,j-1), LPS(i+1,j))
else
    LPS(i,j) = LPS(i+1,j-1) + 2

Вы можете найти блестящее объяснение LPS здесь. Этот парень очень хорошо объясняет, и я настоятельно рекомендую его плейлист для динамического программирования. Конечно, проблема может быть решена с помощью рекурсивного решения (как и любая проблема DP), но здесь я предлагаю пример решения DP:

public static String findLPS(String input) {
    int len = input.length();

    // initializes a diagonal matrix
    int[][] matrix = new int[len][len];
    for (int i = 0; i < matrix.length; i++) {
        matrix[i][i] = 1;
    }

    // finds the length of the longest palindrome subsequence
    for (int jj = 1; jj < len; jj++) {
        int i = 0;
        int j = jj;
        while (i < len && j < len) {
            if (input.charAt(i) == input.charAt(j)) {
                matrix[i][j] = matrix[i + 1][j - 1] + 2;
            } else {
                matrix[i][j] = Math.max(matrix[i + 1][j], matrix[i][j - 1]);
            }
            i++; j++;
        }
    }

    // reconstruct the solution from the matrix
    char[] path = new char[len];
    int i = 0;
    int j = len - 1;

    if (matrix[i][j] == 1) {
        return input.charAt(0) + "";
    }

    while (matrix[i][j] != 0) {
        if (matrix[i][j] == matrix[i + 1][j]) {
            i += 1;
        } else if (matrix[i][j] == matrix[i][j - 1]) {
            j -= 1;
        } else {
            path[i] = input.charAt(i);
            path[j] = input.charAt(j);
            i++; j--;
        }
    }

    String solution = "";
    for (int k = 0; k < len; k++) {
        if (path[k] != 0) {
            solution += path[k];
        }
    }

    return solution;
}