preface

Title link: the longest loop substring

Their thinking

After finishing this problem, I went to see the solution of Leetcode, only to find that there are many methods. My method can be regarded as dynamic programming. The idea is to find the longest return string, which is essentially to find the longest common substring of the string and the cross-string. Of course, even the public substring does have the property that the starting position of the substring in the original string is equal to the ending position of the inverse.

code

class Solution {
  public String longestPalindrome(String s){
        String re = s.charAt(0) +"";// There must be one character by default
        int left = 0, right = s.length() - 1;
        int M = s.length();
        int dp[][] = new int[M+2][M+2];
        for (int i = 1; i <= M; i++)
            for (int j = M; j >= 1; j--) {
                if (s.charAt(i - 1) == s.charAt(j -1)) {
                    dp[i][j] = dp[i - 1][j + 1] + 1;
                    if (dp[i][j] > 1 && Math.abs(dp[i][j] - dp[j][i]) == i - j) {
                        if (re.length() < i - j + 1) {
                            re = s.substring(j - 1, i); }}}}returnre; }}Copy the code

At the end

In this case, the space and time complexity of the solution is O(n^2), and if you want to know more about other solutions, you can go to leetcode and look at other solutions