2472. Maximum Number of Non-overlapping Palindrome Substrings (Leetcode Hard)

Larry solves and analyzes this Leetcode problem as both an interviewer and an interviewee. This is a live recording of a real engineer solving a problem live - no cuts or edits!

#leetcode #coding #programming

[anujjadhav]

Instead of creating a map of int, vector<int> you can just create a map of int, int where in the second one you will store the minimum length of palindrom with length >= k ending at that index. As it can be observed that the best ans will always come with the smallest length substring.

[mohithadiyal]

Memorization approach would also work if used recursion.

[rayahhhmed]

just out of curiosity would a greedy approach work? Like if you store the starts of palindrome length at least k, sort by the starting index and size in increasing order for both, and just see if the intervals collide or not?