1498 Number of Subsequences That Satisfy the Given Sum Condition

1498. Number of Subsequences That Satisfy the Given Sum Condition I hate these array problem and subsequences… This is the daily challenge on 6 May 2023, I opened up the submission tab and found that I tried this problem 1 year ago and from the submission history, I recall how miserable it was… Idea I usually look for two ways to solve array+subsequence problem. DP Two pointers This problem has a test case size of \(10^5\), so DP is out of the game, and two pointer does seem promising....

May 6, 2023 · mimimi

1312 Minimum Insertion Steps to Make a String Palindrome

1312. Minimum Insertion Steps to Make a String Palindrome This is the daily challenge on 22/Apr/2023. Idea To solve this problem, there is one key point that we can’t miss. Assume x is the length of the longest palindromic subsequence, and n is the length of s, the result is simply n-x This is because for those chars that are not in the longest palindromic subsequence, we have to add one char for each of them to make them palindromic....

April 22, 2023 · mimimi

516 Longest Palindromic Subsequence

516. Longest Palindromic Subsequence Idea I re-visited this problem because of another hard problem (1312), and I found that this problem deserves a post on its own. We’re trying to find the longest palindromic subsequence, there are few ways to solve subsequence problems and probably the first one we should consider is Dynamic Programming(DP). DP State We want the longest, so we start from index 0 and index len-1, and takes them if they are the same, do something else if not, so we need to keep track of two indices, left and right....

April 22, 2023 · mimimi