https://www.cnblogs.com/yingp.
this has a JAVA code, you can refer to. I wrote it in C at first. I feel too troublesome. JAVA doesn't know much about it, but I understand a little bit. I hope it can help you

problem solved

because the code provided cannot get correct results for test cases such as opo-upu , after referring to the ideas provided by @studio and Java-- longest common substring problem LCS , the following code is written:

• findLCS (String input): String get the maximum palindromes

  private static String findLCS(String input) {
      // 
      StringBuilder result = new StringBuilder();
  
      // 
      String reverse = new StringBuilder(input).reverse().toString();
  
      // 
      int len = input.length();
  
      //  -> 
      int[][] temp = new int[len][len];
  
      // 
      char[] hor = input.toCharArray();
  
      // 
      char[] ver = reverse.toCharArray();
  
      // ()
      for (int i = 0; i < len; iPP) {
          for (int j = 0; j < len; jPP) {
              temp[i][j] = (hor[j] == ver[i]) ? 1 : 0;
          }
      }
  
      // 
      int horIndex = -1;
      for (int i = 0; i < len - 1; iPP) {
          if (temp[0][i] == 1) {
              horIndex = i;
          }
      }
  
      // 
      int verIndex = -1;
      for (int i = 0; i < len - 1; iPP) {
          if (temp[i][0] == 1) {
              verIndex = i;
          }
      }
  
      //  abcda
      boolean flag = false;
  
      int indexHor = 0;
      if (horIndex != -1 && horIndex != 0) {
          for (int i = horIndex; i < len; iPP) {
              if (temp[indexHorPP][i] == 1) {
                  result.append(hor[i]);
              }
          }
          flag = true;
      }
  
      int indexVer = verIndex;
      if (verIndex != -1) {
          if (flag) {
              result.append("/");
          }
          for (int i = 0; i < len - verIndex; iPP) {
              if (temp[indexVerPP][i] == 1) {
                  result.append(hor[i]);
              }
          }
      }
  
      return result.toString();
  }

• main (String [] args): void main method

  public static void main(String[] args) {
  
      String input1 = "google";
      String input2 = "abcda";
      String input3 = "opo-upu";
  
      System.out.println(input1 + " -> " + findLCS(input1)); // : google -> goog
      System.out.println(input2 + " -> " + findLCS(input2)); // : abcda -> aca
      System.out.println(input3 + " -> " + findLCS(input3)); // : opo-upu -> opo/upu
  
  }

package sun.interview;

import java.util.HashSet;
import java.util.Set;
import java.util.regex.Pattern;

/**
 * @author sunlichao on 2019-07-09.
 */
public class Test1 {

    public static String[] stringFilter(String str) {
        String regEx = "[^a-zA-Z0-9]";
        Pattern p = Pattern.compile(regEx);
        return p.split(str);
    }

    private static void getAllLcs( String a, String b, int[][] mux, int i, int j, String path, Set<String> paths) {

        StringBuilder pathBuilder = new StringBuilder(path);
        while (i > 0 && j > 0) {
            if (a.charAt(i - 1) == b.charAt(j - 1)) {
                pathBuilder.append(a.charAt(i - 1));
                --i;
                --j;
            }else {
                if (mux[i - 1][j] > mux[i][j - 1]) {
                    --i;
                } else if (mux[i - 1][j] < mux[i][j - 1]) {
                    --j;
                } else {
                    getAllLcs(a, b, mux, i - 1, j, pathBuilder.toString(), paths);
                    getAllLcs(a, b, mux, i, j - 1, pathBuilder.toString(), paths);
                    return;
                }
            }
        }
        paths.add(pathBuilder.toString());
    }

    public static String findLCS(String input) {
        if (input == null || input.length() == 0) {
            return "";
        }

        // 
        StringBuilder result = new StringBuilder();

        // 
        String reverse = new StringBuilder(input).reverse().toString();

        // 
        int len = input.length();

        //  -> 
        int[][] tmp = new int[len + 1][len + 1];

        for (int i = 1; i < len + 1; iPP) {
            for (int j = 1; j < len + 1; jPP) {
                if (input.charAt(i - 1) == reverse.charAt(j - 1)) {
                    tmp[i][j] = tmp[i - 1][j - 1] + 1;
                } else {
                    tmp[i][j] = Math.max(tmp[i - 1][j], tmp[i][j - 1]);
                }
            }
        }

        Set<String> paths = new HashSet<>(){};
        Test1.getAllLcs(input, reverse, tmp, input.length(), reverse.length(), "", paths);

        return String.join("/", paths);
    }

    public static String maxs(String input) {
        String[] prepare = stringFilter(input);
        StringBuffer sb = new StringBuffer();
        for (String str : prepare) {
            String result = findLCS(str);
            sb.append(result);
            sb.append("/");
        }
        return sb.substring(0, sb.length()-1);
    }
    public static void main(String[] args) {
        // TODO :goog
        String input1 = "google";

        System.out.println(maxs(input1));
        // TODO 3:aba/aca/ada
        String input2 = "abcda";
        System.out.println(maxs(input2));
        // TODO 2:pop/upup-p
        String input3 = "pop-upu";
        System.out.println(maxs(input3));
    }
}

simply sort out the following ideas: https://www.jianshu.com/p/ac3.