palindromic_substring

dz / leetcode / palindromic_substring

Summary

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

Node Tree

• URL
• cpp_implementation
  • use_of_matrix_structure
    • error_in_comments
  • dynamic_programming
  • error_in_comments
• intuition_pre_hint
  • brute_force
  • expand_from_centers
  • intuition_post_hint
    • dynamic_programming
• leetcode_editorial
  • manachers_algorithm
  • brute_force
  • dynamic_programming
  • expand_from_centers

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	brute_force, expand_from_centers (thought about this here), intuition_post_hint (after reading the hint)
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	use_of_matrix_structure, dynamic_programming (what the C++ implementation was trying to do), error_in_comments

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	use_of_matrix_structure, cpp_implementation

leetcode_editorial
content	leetcode editorial
children	manachers_algorithm (Fastest solution, advanced and out of scope), brute_force, dynamic_programming, expand_from_centers
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	intuition_pre_hint, leetcode_editorial

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	intuition_pre_hint, leetcode_editorial

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