Click here to read more about algorithmic interviewing

Topic describes

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

Example 1:

Input: s = “babad” Output: “bab”

Explanation: “ABA” is also a suitable 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 numbers and English letters (uppercase and/or lowercase)

---

Simple solution

An easy way to think about this problem is to enumerate each bit of string S as the center of the palindrome string, expanding left and right until the boundary is reached or the palindrome string definition is not satisfied.

This must be the right line of thinking.

But it’s obviously a naive approach, so how do we know if it’s feasible?

Remember what we did in the last section? When we have a simple implementation method, we need to start from the data size of the topic, the processing speed of the computer and the amount of calculation of the implementation method, to judge whether this approach will not time out.

Since the string length is only 1000 at most, and our method is O(n^2), our algorithm should be less than 10^6, within the range of computer processing per second.

First enumerate the center I of the palindrome string, and then extend the boundary to both sides in two cases until the boundary is reached or the palindrome string definition is not satisfied:

• If the palindrome string length is odd, s[I − k] == s[I + k], k = 1,2,3…

• If the palindrome string length is even, s[I − k] == S [I + K − 1], k = 1,2,3…

class Solution {
    public String longestPalindrome(String s) {
        String ans = "";
        for (int i = 0; i < s.length(); i++) {
            // The palindrome string is odd
            int l = i - 1, r = i + 1;
            String sub = getString(s, l, r);
            if (sub.length() > ans.length()) ans = sub;

            // The palindrome string is even
            l = i - 1;
            r = i + 1 - 1;
            sub = getString(s, l, r);
            if (sub.length() > ans.length()) ans = sub;
        }
        return ans;
    }
    String getString(String s, int l, int r) {
        while (l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) {
            l--;
            r++;
        }
        return s.substring(l + 1, r); }}Copy the code

Time complexity: enumerates each character in S as the center point of the palindrome string, and then extends left and right from the center point to the boundary at most. It’s O(n2)O(n^2)O(n2).

Space complexity: O(1)O(1)O(1)

---

Manacher algorithm

This is a relatively unpopular algorithm, the scope of use is relatively single, can only be used to solve the “palindrome string” problem.

Manacher is indeed the optimal solution to the palindrome string problem.

But even for all the “palindrome string” problems in LeetCode, none of them have to go through O(n) Manacher algorithm to AC.

So I’m going to go straight to the solution (which can be used as a template) and not talk about how the algorithm works.

Manacher algorithm is quite long. In order to avoid the discussion on the split case of even and odd palindrome string length, I will process the original characters and insert placeholders between the boundary and characters.

After using this technique, when the non-placeholder character is the center of the palindrome string, the palindrome string length is odd; When the placeholder character is the center of a palindrome string, the palindrome string length is even.

Here’s an example:

Original character: “babad”, after conversion: “*b*a* B *a* D *”, the resulting palindrome string: “* B *a* B *”, and then remove the placeholder output: “bab”.

Explanation: “ABA” is also a suitable answer to the question.

class Solution {
    public String longestPalindrome(String s) {
        if (s.length() == 1) return s;

        char[] chars = manacherString(s);
        int n = chars.length;
        int[] pArr = new int[n];
        int C = -1, R = -1, pos = -1;
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < n; i++) {
            pArr[i] = i < R ? Math.min(pArr[C * 2 - i], R - i) : 1;
            while (i + pArr[i] < n && i - pArr[i] > -1) {
                if (chars[i + pArr[i]] == chars[i - pArr[i]]) {
                    pArr[i]++;
                } else {
                    break; }}if (i + pArr[i] > R) {
                R = i + pArr[i];
                C = i;
            }
            if(pArr[i] > max) { max = pArr[i]; pos = i; }}int offset = pArr[pos];
        StringBuilder sb = new StringBuilder();
        for (int i = pos - offset + 1; i <= pos + offset - 1; i++) {
            if(chars[i] ! =The '#') sb.append(chars[i]);
        }
        return sb.toString();
    }
    char[] manacherString(String s) {
        char[] chars = new char[s.length() * 2 + 1];
        for (int i = 0, idx = 0; i < chars.length; i++) {
            chars[i] = (i & 1) = =0 ? The '#' : s.charAt(idx++);
        }
        returnchars; }}Copy the code

Time complexity: The string is scanned only once. The complexity is O(n)O(n)O(n)

Space complexity: O(1)O(1)O(1)

---

conclusion

In addition to providing the conventional O(n2)O(n^2)O(n2) solution, sanye also provides you with the Manacher algorithm template for the optimal solution of “palindrome string”. It is recommended that students who are able to learn it by heart.

The point of memorizing such an algorithm is that you have an O(n)O(n)O(n) O(n) API in your brain to use, which passes in a string and returns the largest substring of that string.

At the same time, with the help of Manacher algorithm, it also introduces how to avoid the case discussion of palindrome string length. This technique is applicable as long as the “palindrome string” problem is involved (whether or not using Manacher algorithm).

For students who want to recite Manacher’s algorithm, it is suggested to type 3 times and write 2 times silently, then after 24 hours, write 2 times silently again, a week later, and then repeat, until proficient.

Don’t be afraid to forget. Forgetting is normal and muscle memory can be formed with a few repetitions. All of the contestants who occupy the first page of LeetCode weekly are extremely skilled in algorithmic routines and templates. Come on ~

---

The last

This is the no.5 of our “Brush through LeetCode” series, which started on 2021/01/01. There are 1916 topics in LeetCode as of the start date, some of which have locks. We will finish all the topics without locks first.

In this series of articles, in addition to explaining how to solve the problem, I will also present the most concise code possible. If a general solution is involved, the corresponding code template will also be used.

As the number of LeetCode questions keeps increasing with weekly and biweekly competitions, in order to facilitate our progress statistics, we will calculate the progress according to the total number of questions at the beginning of the series as the denominator and the completed questions as the numerator. Current progress is 5/1916.

In order to facilitate the students to debug and submit the code on the computer, I set up the relevant warehouse: Github address & Gitee address.

In the repository, you’ll see links to the series, the corresponding code for the series, the LeetCode source links, and some other preferred solutions.

# Algorithms and data structures

# LeetCode antithesis

# Algorithmic interview