algo-en
  • Introduction
  • I. Dynamic Programming
    • Dynamic Programming in Details
    • Classic DP: Edit Distance
    • Classic DP: Super Egg
    • Classic DP: Super Egg(Advanced Solution)
    • Class DP: Longest Common Subsequence
    • Classis DP: Game Problems
    • Regular Expression
    • The Strategies of Subsequence Problem
    • Greedy: Interval Scheduling
    • 4 Keys Keyboard
    • What is DP Optimal Substructure
    • Longest Increasing Subsequence
    • KMP Algorithm In Detail
    • House Robber Problems
    • Stock Buy and Sell Problems
  • II. Data Structure
    • Binary Heap and Priority Queue
    • LRU Cache Strategy in Detail
    • Collections of Binary Search Operations
    • Special Data Structure: Monotonic Stack
    • Special Data Structure: Monotonic Stack
    • Design Twitter
    • Reverse Part of Linked List via Recursion
    • What's the Best Algo Book
    • Queue Implement Stack/Stack implement Queue
    • Framework for learning data structures and algorithms
  • III. Algorithmic thinking
    • My Way to Learn Algorithm
    • The Framework for Backtracking Algorithm
    • Binary Search in Detail
    • The Tech of Double Pointer
    • The Key Concept of TwoSum Problems
    • Divide Complicated Problem: Implement a Calculator
    • Prefix Sum Skill
    • FloodFill Algorithm in Detail
    • Interval Scheduling: Interval Merging
    • Interval Scheduling: Intersections of Intervals
    • String Multiplication
    • Pancake Soring Algorithm
    • Sliding Window Algorithm
    • Some Useful Bit Manipulations
    • Russian Doll Envelopes Problem
    • Recursion In Detail
    • Backtracking Solve Subset/Permutation/Combination
    • Several counter-intuitive Probability Problems
    • Shuffle Algorithm
  • IV. High Frequency Interview Problem
    • How to Implement LRU Cache
    • How to Find Prime Number Efficiently
    • How to Calculate Minimium Edit Distance
    • How to Solve Drop Water Problem
    • How to Remove Duplicate From Sorted Sequence
    • How to Find Longest Palindromic Substring
    • How to Reverse Linked List in K Group
    • How to Check the Validation of Parenthesis
    • How to Find Missing Element
    • How to Pick Elements From a Arbitrary Sequence
    • How to use Binary Search
    • How to Scheduling Seats
    • Union-Find Algorithm in Detail
    • Union-Find Application
    • Find Subsequence With Binary Search
    • Problems can be solved by one line
    • How to Find Duplicate and Missing Element
    • How to Check Palindromic LinkedList
  • V. Common Knowledge
    • Difference Between Process and Thread in Linux
    • You Must Know About Linux Shell
    • You Must Know About Cookie and Session
    • Cryptology Algorithm
    • Some Good Online Pratice Platforms
Powered by GitBook
On this page
  • 1. Thinking
  • 2. Implementation

Was this helpful?

  1. IV. High Frequency Interview Problem

How to Find Longest Palindromic Substring

PreviousHow to Remove Duplicate From Sorted SequenceNextHow to Reverse Linked List in K Group

Last updated 5 years ago

Was this helpful?

Author:

Translator:

Palindrome questions are very common in the interview, this article provides some insights about palindromic problem.

To specific :

A palindrome is a word, number, phrase, or other sequence of characters which reads the same backward as forward, such as madam, racecar.

For example: aba and abba are both palindromic, because they are symetric strings, that you can read each of them in reversed order, and you can just get a same string.

Notice: palindrome string could be in either odd length or even length, a good solution would be double pointers. Next, I'll show you how doulbe pointers work in a real leetcode problem.

string longestPalindrome(string s) {}

1. Thinking

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

A very interesting pespective: 1. Reversing s in to s' 2. Finding the longest common substring.

For instance, a string abacd, a reversed version is dcaba, and the longest common string is aba, seemingly perfect.

However, it would be wrong when we apply to aacxycaa, which a reversed version would be aacyxcaa, then the longest common substring turns out to be aac. But, what we need should be aa.

Although this way has its faults, we can still get some inspirations that we can transform a problem seemingly hard into another simpler problem that we can understand easier.

Now, the double pointers

Core idea: start a scanner from the mid point of the string we represent the idea into pseudo code:

for 0 <= i < len(s):
    find a palindrome that set s[i] as its mid point
    update the answer

When the length of string is even, for instance: abba, the code above would not work.

So, a better version here :

for 0 <= i < len(s):
    find a palindrome that set s[i] as its mid point
    find a palindrome that set s[i] and s[i + 1] as its mid point
    update the answer

PS: you may encounter some problems like : outofIndex error. Don't worry, we'll fix them later.

2. Implementation

a function implementation:

string palindrome(string& s, int l, int r) {
    // avoid outOfIndex error
    while (l >= 0 && r < s.size()
            && s[l] == s[r]) {
        // scanning toward both directions
        l--; r++;
    }
    // return a palindrome that set s[l] and s[r] as mid point
    return s.substr(l + 1, r - l - 1);
}

Why we need both pointer l and pointer r? In this way, we can handle palindrome strings in odd and even length

for 0 <= i < len(s):
    # find a palindrome that set s[i] as its mid 
    palindrome(s, i, i)
    # find a palindrome that set s[i] and s[i + 1] as its mid  
    palindrome(s, i, i + 1)
    update the answer

Completed code solution:

string longestPalindrome(string s) {
    string res;
    for (int i = 0; i < s.size(); i++) {
        // find a palindrome that set s[i] as its mid 
        string s1 = palindrome(s, i, i);
        // find a palindrome that set s[i] and s[i + 1] as its mid  
        string s2 = palindrome(s, i, i + 1);
        // res = longest(res, s1, s2)
        res = res.size() > s1.size() ? res : s1;
        res = res.size() > s2.size() ? res : s2;
    }
    return res;
}

Thus, this leetcode problem is solved. Now, we get:

Time complexity: O(N^2)

Space complexity: O(1)

By the way, a dynamic programming approach can also work in this problem in a same time complexity. However, we need at least O(N^2) spaces to store DP table. Therefore, in this problem, dp approach is not the best solution.

In addition, Manacher's Algorithm requires only O(N) time complexity. You readers can search it through the Internet by your own interests. It should be very interesting.

Stick to original high-quality articles, and strive to make clear the algorithm problems. Welcome to follow my Wechat official account "labuladong" for the latest articles.

labuladong
Lrc123
reference