RishBlogs

Dynamic Programming: longest palindromic subsequence

466C-Number Of Ways
Instead of binary search, a suffix sum array of count can be created for quering for each \(l[i]\). Reducing complexity from \(O(n\log{}n)\) to \(O(n)\).


1114D-Flood Fill
One interesting idea to note was, the answer can be calculated using longest palindromic subsequence. Which inturn can be calculated by find LCS between array and it’s reverse.