"""
Solution for 1312. Minimum Insertion Steps to Make a String Palindrome
https://leetcode.com/problems/minimum-insertion-steps-to-make-a-string-palindrome/
"""
from functools import lru_cache

class Solution:
  """
  Runtime: 796 ms, faster than 78.99% of Python3 online submissions for Minimum Insertion Steps to Make a String Palindrome.
  Memory Usage: 169.6 MB, less than 100.00% of Python3 online submissions for Minimum Insertion Steps to Make a String Palindrome.
  """
  def minInsertions(self, s: str) -> int:
    """
    Given a string s. In one step you can insert any character at any index of the string.

    Return the minimum number of steps to make s palindrome.

    A Palindrome String is one that reads the same backward as well as forward.



    Example 1:

    Input: s = "zzazz"
    Output: 0
    Explanation: The string "zzazz" is already palindrome we don't need any insertions.
    Example 2:

    Input: s = "mbadm"
    Output: 2
    Explanation: String can be "mbdadbm" or "mdbabdm".
    Example 3:

    Input: s = "leetcode"
    Output: 5
    Explanation: Inserting 5 characters the string becomes "leetcodocteel".
    Example 4:

    Input: s = "g"
    Output: 0
    Example 5:

    Input: s = "no"
    Output: 1


    Constraints:

    1 <= s.length <= 500
    All characters of s are lower case English letters.

    Args:
      s:

    Returns:

    """
    @lru_cache(maxsize=None)
    def lps(i, j):
      if i > j:
        return 0
      if i == j:
        return 1
      if s[i] == s[j]:
        return lps(i + 1, j - 1) + 2
      return max(lps(i + 1, j), lps(i, j - 1))

    return len(s) - lps(0, len(s) - 1)

  def top_down(self, s: str) -> int:
    """
    A solution using top-down approach that runs in O(N^2) in time and O(N^2) in
    space

    Args:
      s:

    Returns:

    """
    @lru_cache(maxsize=None)
    def lps(i, j):
      if i >= j:
        return 0
      if s[i] == s[j]:
        return lps(i + 1, j - 1)
      return min(lps(i + 1, j), lps(i, j - 1)) + 1

    return lps(0, len(s) - 1)
