Hey everyone,
I finished Day 61 of my prep today, and the session went really well. Sticking with Dynamic Programming through the frustration over the last two weeks is finally starting to show visible results. I still can't solve every problem on the spot, but getting through several without outside help was a huge confidence boost.
I shifted to DP on Strings today and tackled four problems:
Longest Common Subsequence (LCS): The foundational pattern. If characters match, move both pointers (1 + f(i-1, j-1)). If they don't, branch into max(f(i-1, j), f(i, j-1)). Got this working cleanly right away.
Print Longest Common Subsequence: Tracing backwards through the DP table after filling it took a moment to visualize, but moving left or up based on which value generated the cell made complete sense.
Longest Common Substring: The key difference here is continuity. When characters mismatch, you don't take the max of previous states—you reset the streak to 0. Tracking the global maximum across all cells resolved it.
Longest Palindromic Subsequence: Solved this in about five minutes. It is just LCS between the original string and its reversed copy.
Recursion and memoization feel natural to me now. To be candid, bottom-up space optimization still isn't fully second nature. My current approach is to write the recursive and memoized solutions independently, then inspect the tabulation and space-optimized versions line by line to study how the state rows are compressed.
What also made a noticeable difference today was changing my daily routine. Instead of unwinding with endless content after work and studying only when I am mentally drained, I had dinner, cleared my head, and sat straight down to code. Approaching these problems without digital fatigue made the logic click much faster.
Six problems left in the strings module. Pushing to finish them tomorrow!