This is the fifth day of my participation in the August More text Challenge. For details, see: August More Text Challenge

The title

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

The sample1: Enter: s ="babad"Output:"bab"Explanation:"aba"The same is true of the question.Copy the code

The sample2: Enter: s ="cbbd"Output:"bb"
Copy the code

The sample3: Enter: s ="a"Output:"a"
Copy the code

The sample4: Enter: s ="ac"Output:"a"
Copy the code

Tip:1 <= s.length <= 1000S consists only of numbers and Letters (upper and/or lower case)Awesome!.680Submit the number1.909.975
Copy the code

A little thought

Those of you who have seen my series know that the main point of this is to tell you what I think, and the first thing that comes to mind when I look at this is,The oldest string with no duplicate charactersWhen using the sliding window to solve has forgotten the small partner can go back to see. But obviously not in today’s problem, I started with a very simple idea that you’ve done the problem of judging palindromes! Then each substring is judged to find the largest, this violence enumeration method. I looked at the requirements1 <= s.length <= 1000The numbers are fine. So the violence enumeration might time out. I mean maybe I didn’t try it, but if you’re interested, you can try itDon’t call me lazy. Probably not. So what’s the solution to this problem? See below.

Officially opened lu

Judge palindrome strings

Either way it’s a palindrome string so let’s talk about that first. What is palindrome string I will not say this will not own Baidu. Judgment Method 1:As shown in figure ifiThe character pointing to is equal tojI’m going to move the two Pointers inward and then I’m going to say, if there’s a pair that doesn’t match, it’s not. That’s for odd characters and it’s also for even characters.

Judgment method 2:If it’s odd we start with the middle character, if it’s even we start with the middle two charactersiandjWhether the characters in the position of is equal or not is not. These two methods you can try to write according to your own ideas.

My way of doing it

Inspired by the second judgment method, we find a solution called the central diffusion method and the judgment idea is almost the same: the boundary case is the case where the length of the substring is 1 or 2. We enumerate each of these boundary cases, starting with the corresponding substring and expanding on both sides. If the letters on both sides are the same, we can continue to expand, for example from P(I +1,j-1)P(I +1,j−1) to P(I,j)P(I,j); If the letters on both sides are different, we can stop the expansion, because any substring after that can’t be a palindrome. First write out the method of judgment:

public int expandAroundCenter(String s, int left, int right) {
		// If one of these conditions is not met, the loop will be broken
        while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
            --left;
            ++right;
        }
        return right - left - 1;
    }

Copy the code

Let’s look at the principal function

public String longestPalindrome(String s) {
		// This is mainly a luck card, and usually does not give you a character test, of course we need to be careful
        if (s == null || s.length() < 1) {
            return ;
        }
        int fei = 0, xue = 0;
        // Spreads from the first element of the string
        for (int i = 0; i < s.length(); i++) {
            // Start with an odd number of substrings
            int len1 = expandAroundCenter(s, i, i);
            // Assume an even substring
            int len2 = expandAroundCenter(s, i, i + 1);
            // Compare the two
            int len = Math.max(len1, len2);
            // Find the new maximum palindrome string
            if (len > end - start) {
                start = i - (len - 1) / 2;
                end = i + len / 2; }}// Return this string
        return s.substring(fei, end + 1);
    }
Copy the code

About this approach:

substring(int beginIndex, int endIndex)
Copy the code

Let’s just test it out a little bit in case the big boys don’t know, or try it out the way I talked about it last time.

public static void main(String[] args) {
		String a="sfjls";
		System.out.println(a.substring(2.4));
		System.out.println(a.substring(2)); } Result jl JLSCopy the code

So let’s get a feel for it. Ok, so that’s the algorithm for today and I’ll see you tomorrow.