Leetcode Problem 1312. Minimum Insertion Steps to Make a String Palindrome

1312. Minimum Insertion Steps to Make a String Palindrome

Leetcode Solutions

Dynamic Programming with Space Optimization

  1. Initialize n to the length of s.
  2. Create sReverse as the reverse of s.
  3. Initialize two 1D arrays dp and dpPrev of size n + 1 with zeros.
  4. Iterate over s and sReverse using two nested loops.
  5. For each pair (i, j), check if s[i - 1] == sReverse[j - 1].
  6. If they match, set dp[j] = 1 + dpPrev[j - 1].
  7. If they don't match, set dp[j] = max(dpPrev[j], dp[j - 1]).
  8. After the inner loop, copy dp to dpPrev.
  9. The length of the LPS is dp[n].
  10. Return n - dp[n] as the minimum number of insertions.
UML Thumbnail

Iterative Dynamic Programming

Ask Question

Programming Language
image/screenshot of info(optional)
Full Screen
Loading...

Suggested Answer

Answer
Full Screen
Copy Answer Code
Loading...