leetcode/palindromic_substring

palindromic_substring

dz / leetcode / palindromic_substring

Summary

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

Node Tree

Nodes

URL
content URL
hyperlink https://leetcode.com/problems/longest-palindromic-substring

intuition_pre_hint
content The brute-force approach I imagine would involve taking each character, and then sweeping backwards from the end of string, check every matching character to see if the region marks a palindrome. Palindromes can be split in half, which means the largest segment a palindrome can be is N/2. There might be a way to use this property to make a more efficient algorithm, perhaps a sliding window. Another approach: finding potential palindromes starting at the center, and working backwards. The smallest possible even palindrome is two duplicate letters. The smallest possible odd palindrome is 3 letters (not counting 1 letter), with a center letter and two duplicate letters on the outside. You could do a linear sweep for even/odd palindromes, and upon finding one, expand the palindrome out on either end and check the size.
children expand_from_centers (thought about this here), intuition_post_hint (after reading the hint), brute_force
remarks There's a hint on the leetcode website that I'm ignoring for the moment. So my thoughts here are just reading the problem.

intuition_post_hint
content The language of the 3 uses terms like "re-use previously computed palindrome", which suggests a solution using recursion and/or dynamic programming. My initial thoughts finding palindrome centers seems close. Apparently the O(n) palindrome checks in brute force can be reduced to O(1). So, that seems like a data structure.
children dynamic_programming (what I thought of after reading the hints)
parents intuition_pre_hint
remarks thoughts after reading the hint

cpp_implementation
content C++ implementation of solution
children error_in_comments, use_of_matrix_structure, dynamic_programming (what the C++ implementation was trying to do)

use_of_matrix_structure
content Use of matrix data structure. Still trying to grok this, though the comments are helpful. I should have read the constraints of the string length (max length 1000), that would have been a good hint.
children error_in_comments (reading comments about matrix)
parents cpp_implementation

error_in_comments
content I think the comments here are incorrect. I believe it is erroneously saying "abbcba" is the longest palindrome.
parents cpp_implementation, use_of_matrix_structure

leetcode_editorial
content leetcode editorial
children expand_from_centers, manachers_algorithm (Fastest solution, advanced and out of scope), brute_force, dynamic_programming
hyperlink https://leetcode.com/problems/longest-palindromic-substring/editorial

dynamic_programming
content The dynamic programming algorithm is basically what the C++ solution was attempting to do. The LC algorithm uses a boolean table, while the C++ solution I think keeps track of the sizes? The answer they come to is incorrect when they work it out in the comments, so I'm mildly skeptical this is a correct algorithm.
parents leetcode_editorial, intuition_post_hint, cpp_implementation

expand_from_centers
content "Expand from centers" seems to be the line of thinking I came to when I was thinking about the problem.
parents leetcode_editorial, intuition_pre_hint

brute_force
content I think I mostly described the brute force solution correctly, although the editorial has a more elegant way of describing it: check all substrings for palindromes.
parents leetcode_editorial, intuition_pre_hint

manachers_algorithm
content Manachers Algorithm for finding the longest palindromic string in O(n) time. Faster because it re-uses precomputed data when a palindrome exists inside another palindrome.
parents leetcode_editorial
hyperlink https://en.wikipedia.org/wiki/Longest_palindromic_substring#Manacher%27s_algorithm