This is the 8th day of my participation in the November Gwen Challenge. Check out the event details: The last Gwen Challenge 2021

The title

Given a string s, find the longest substring in s.

Example 1:

Input: s = “babad” Output: “bab” Explanation: “ABA” is also the answer to the question. Example 2:

Input: s = “CBBD” Output: “bb” Example 3:

Input: s = “a” Output: “a” Example 4:

Input: s = “AC”

Tip:

1 <= S. length <= 1000 s Consists of only digits and letters (uppercase and/or lowercase)

Train of thought

So in order to do this problem you need to understand what are palindromes and substrings

  1. Palindrome: The order from left to right is the same as from right to left, with the property of axial symmetry
  2. Substring: A substring is a contiguous part of the original string

Since it is axially symmetric, the first thing that comes to mind is that the string on the axis expands to the two sides, so there are two more situations

  1. Odd symmetry, such as “bab,” requires comparing the left and right characters to see if they are equal
  2. Even symmetry, such as the “baab” form, requires comparisons between current and left and right

Code implementation

public static String longestPalindrome(String s) {
    // There is no need to save the substring, just remember the starting position and length
    int maxStart = 0, maxLen = 0;
    for (int i = 0; i < s.length(); i++) {
        int left = i - 1;
        int right = i + 1;
        int currLen = 1;
        // Even symmetry, the current character is equal to the left character, the length of the substring +1
        while (left >= 0 && s.charAt(left) == s.charAt(i)) {
            currLen++;
            left--;
        }
        // Even is symmetric, the current character is equal to the right character, and the length of the substring is +1
        while (right < s.length() && s.charAt(right) == s.charAt(i)) {
            currLen++;
            right++;
        }
        // Odd symmetry, the left and right sides of the current character are equal, and the length of the substring is +2
        while (left >= 0 && right < s.length() && s.charAt(right) == s.charAt(left)) {
            currLen = currLen + 2;
            left--;
            right++;
        }
        if(currLen > maxLen) { maxLen = currLen; maxStart = left; }}return s.substring(maxStart + 1, maxStart + maxLen + 1);
}
Copy the code

Execution time: 44 ms, beating 60.33% of all Java commits

Memory consumption: 38.1 MB, beating 97.80% of all Java commits

To optimize the

In fact, the above solution does a lot of double calculation, dynamic programming is to reduce the problem of double calculation. Dynamic programming sounds fancy. In fact, it is space for time, the results of the calculation of temporary storage, to avoid double calculation.

Palindromes have the nature of state transition: after a palindrome is removed, the remaining part is still a palindrome. On the other hand, if the first and last characters of a string are not equal, the string must not be a palindrome. The method of dynamic programming follows from this property.

Step 1: define the state dp[I][j] indicates whether the substring S [I..j] is a returnee substring, where the substring S [I..j] is defined as the left closed and right closed interval, that is, s[I] and S [j] can be obtained.

Step 2: According to whether the beginning and end characters are equal, the state transition equation deduces whether the string is palindrome or not depending on whether the end is palindrome or not

dp[i][j] = (s[i] == s[j]) and dp[i + 1][j - 1]

Step 3: Initialize

Initialize a Boolean array with a flag bit to indicate whether it is a palindrome

public String longestPalindrome(String s) {
    if (s == null || s.length() < 2) {
        return s;
    }
    
    int maxStart = 0;  
    int maxEnd = 0;    
    int maxLen = 1;  

    boolean[][] dp = new boolean[s.length()][s.length()];
    for (int r = 1; r < s.length(); r++) {
        for (int l = 0; l < r; l++) {
            //r +1 <= 2; r +1 <= 2; r +1 <= 2
            if (s.charAt(l) == s.charAt(r) && (r - l <= 2 || dp[l + 1][r - 1])) {
                dp[l][r] = true;
                if (r - l + 1 > maxLen) {
                    maxLen = r - l + 1; maxStart = l; maxEnd = r; }}}}return s.substring(maxStart, maxEnd + 1);
}
Copy the code

summary

This problem began to involve common dynamic planning ideas, and then encountered several dynamic planning problems, will try to summarize the template of dynamic planning, so that after encountering again will not be confused, at least some ideas.