Offer to come, dig friends take it! I am participating in the 2022 Spring Recruit Punch card activity. Click here for details.

1. Title Description

Source: LeetCode

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”

Tip:

  • 1 <= s.length <= 1000
  • S consists of only numbers and letters

Second, train of thought analysis

  • The idea is that a substring is symmetric from the center to the sides, so we can simply iterate over each character in S as if it were the center of the substring, and expand the two sides as much as possible until we are not satisfied.
  • In this case, the length is the length of the substring, and finding the largest is the final result.

Three, code implementation

class Solution { public String longestPalindrome(String s) { int start = 0; int end = 0; for (int i = 0; i < s.length(); i++) { int len1 = expandAroundCenter(s, i, i); int len2 = expandAroundCenter(s, i, i + 1); int len = Math.max(len1, len2); if (len > end - start) { start = i - (len - 1) / 2; end = i + len / 2; } } return s.substring(start, end + 1); } private int expandAroundCenter(String s, int left, int right) { while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) { left--; right++; } return right - left - 1; }}Copy the code

The results

Complexity analysis

Time complexity: O(n2)O(n^2)O(n2), where n is the length of the string. Space complexity: O(1)O(1)O(1).

4. Better solution

There’s a better way to do it, which is called the Manacher algorithm

If you are interested, please read the problem solution written by Windliang

Manacher’s Algorithm is a linear method for finding the longest substring of a string. It was invented by a man named Manacher in 1975. The greatest contribution of this method is to improve the time complexity to linearity.

First, we solve the odd and even problems by inserting “#” between each character, and in order to make the extension process automatically end when it reaches the boundary, we insert “^” and “$” at both ends, respectively, two characters that cannot appear in the string, so that when the center is expanded, we can determine whether the characters at both ends are equal. If you get to the boundary you have to be unequal, and you have a loop. After processing, the length of the string is always odd.

First we use an array P to hold the maximum number extended from the center, which happens to be the total length of the original string with the “#” removed. For example, in the figure below, where the subscript is 6, you can see that P[6] is equal to 5, so it extends by 5 characters from the left, and by 5 characters from the right, which is “#c#b#c#b#c#”. Remove the # and restore the string to “CBCBC”, which is exactly 5 in length.

To find the index of the original string, subtract P [I] from P and divide by 2.

For example, we find that the maximum value of P[I] is 5, that is, the maximum length of the palindrome string is 5, and the corresponding subscript is 6, so the initial subscript of the original string is (6-5) / 2 = 0. So we just need to return bits 0 through (5-1) of the original string.

Finding each P [I] is the key to the algorithm, which takes full advantage of the symmetry of palindromic strings.

We use C for the center of the palindrome string and R for the right radius of the palindrome string. So R is equal to C plus P[I]. The palindrome strings corresponding to C and R are the right-most palindrome strings of R in the current loop.

Let’s consider the P [I] as shown below.

Use i_mirror to indicate the subscript of the ith character about C.

So now we want P [I], if we’re using the center extension, we just extend it to both sides. But we can actually use the symmetry of the palindrome string C. The point of symmetry of I with respect to C is i_mirror, P [i_mirror] = 3, so P [I] is also equal to 3.

However, there are three cases in which a direct assignment of P [i_mirror] would be incorrect, as discussed below.

  1. Beyond the R

When we ask for P [I], P [mirror] = 7, and at this point P [I] does not equal 7, why, because we start from I 7, equals 22, has exceeded the right of R, can not use symmetry at this point, but we can certainly extend to R, So P [I] is at least equal to R – I = 20-15 = 5, is it bigger? We just compare the symmetry points of T [R+1] and T [R+1] with respect to I, just like center extension.

  1. P [i_mirror] encounters the left edge of the original string

P [i_mirror] = 1; P [I] = 1; P [i_mirror] = 1; To stop the cycle. P [I] does not have a boundary, so we can continue to expand both sides step by step by center extension.

  1. I is equal to R

In this case, we assign P [I] to 0, and then expand step by step through the center expansion method.

Consider the update of C and R and thus compute each P [I] step by step. When the right boundary of the evaluated P [I] is greater than the current R, we need to update C and R to the current palindrome string. Because we have to keep I in R, we have to update R as soon as there’s an R to the right.

The right boundary of P [I] will be 10 + 3 = 13, so it is greater than the current R. We need to update C to the value of I, which is 10, and R to 13. Continue the loop.

code

public String preProcess(String s) { int n = s.length(); if (n == 0) { return "^$"; } String ret = "^"; for (int i = 0; i < n; i++) ret += "#" + s.charAt(i); ret += "#$"; return ret; } // Public String gestPalindrome2(String s) {String T = preProcess(s); int n = T.length(); int[] P = new int[n]; int C = 0, R = 0; for (int i = 1; i < n - 1; i++) { int i_mirror = 2 * C - i; if (R > i) { P[i] = Math.min(R - i, P[i_mirror]); R} else {P[I] = 0; While (t.charat (I + 1 + P[I]) == t.charat (I - 1 - P[I])) {P[I]++; } if (I + P[I] > R) {C = I; R = i + P[i]; Int maxLen = 0; int centerIndex = 0; for (int i = 1; i < n - 1; i++) { if (P[i] > maxLen) { maxLen = P[i]; centerIndex = i; } } int start = (centerIndex - maxLen) / 2; Return s.substring(start, start + maxLen); return s.substring(start, start + maxLen); }Copy the code

conclusion

The first thing that comes to mind is that we want to do something a little bit more naive

For Manacher algorithm, we need to take a step to understand, and more practice familiar.