title: Dynamic Programming Set 28 Minimum Insertions To Form A Palindrome
signature: function dynamic_programming_set_28_minimum_insertions_to_form_a_palindrome(str, l, h)
source_py: def dynamic_programming_set_28_minimum_insertions_to_form_a_palindrome(str, l, h):
      if (l > h):
          return sys.maxsize
      if (l == h):
          return 0
      if (l == (h - 1)):
          return (0 if (str[l] == str[h]) else 1)
      if (str[l] == str[h]):
          return dynamic_programming_set_28_minimum_insertions_to_form_a_palindrome(str, (l + 1), (h - 1))
      else:
          return (min(dynamic_programming_set_28_minimum_insertions_to_form_a_palindrome(str, l, (h - 1)), dynamic_programming_set_28_minimum_insertions_to_form_a_palindrome(str, (l + 1), h)) + 1)
source_cpp: int dynamic_programming_set_28_minimum_insertions_to_form_a_palindrome(vector<char> str, int l, int h) {
    if ( l > h ) return INT_MAX;
    if ( l == h ) return 0;
    if ( l == h - 1 ) return ( str [ l ] == str [ h ] ) ? 0 : 1;
    return ( str [ l ] == str [ h ] ) ? dynamic_programming_set_28_minimum_insertions_to_form_a_palindrome ( str, l + 1, h - 1 ) : ( min ( dynamic_programming_set_28_minimum_insertions_to_form_a_palindrome ( str, l, h - 1 ), dynamic_programming_set_28_minimum_insertions_to_form_a_palindrome ( str, l + 1, h ) ) + 1 );
  }
question_info.test_code: 
  
  -- SOLUTION CODE
  -- ============================================
  PLACEHOLDER_CODE_BODY
  
  -- TESTING CODE 
  -- ============================================
  function isCorrect(actual, expected)
      if type(expected) ~= type(actual) then
          return false
      end
      
      if type(expected) == 'table' then
          for k,v_expected in pairs(expected) do
              
              if actual[k] == nil then
                  return false
              end
              local v_actual = actual[k]
              if not isCorrect(v_actual, v_expected) then
                  return false
              end
              actual[k]=nil
          end
      
          if next(actual) then 
              return false
          end
          return true
      else
          return actual == expected
      end
  end
  
  function validateSolution(actual, expected)
      return isCorrect(actual,expected)
  end
  
  function driver(str, l, h, expected)
      local exec_result;
      local status, error_msg = pcall(function () 
          exec_result=PLACEHOLDER_FN_NAME(str, l, h) 
      end)
      if status then
          if validateSolution(exec_result,expected) then
              return "PASSED"
          end
          return "FAILED"
      else
          return string.format("ERROR=%s",string.gsub(error_msg,".*:[%d]+: ",""))
      end
  end
      
  function main()
      result = driver({'F', 'F', 'J', 'K', 'K', 'L', 'P', 'S', 'T', 'V', 'W', 'Y', 'b', 'd', 'j', 'l', 't', 'u', 'x', 'y'}, 11, 11, 0)
      print(string.format("TEST-0...%s",result))
  
      result = driver({'0', '1', '8', '8', '8', '4', '4', '3', '9', '6', '5', '2', '8', '2', '0', '2', '6', '0', '7', '7', '3', '2', '4', '5', '9', '7', '2', '4', '1', '8', '7', '9', '8', '0', '8', '5', '4', '2', '3'}, 19, 22, 3)
      print(string.format("TEST-1...%s",result))
  
      result = driver({'1'}, 0, 0, 0)
      print(string.format("TEST-2...%s",result))
  
      result = driver({'g', 'y', 'r', 'M', 'v', 'z', ' ', 'k', 'S', 'P', 'x', 'p', 'E', 'z', 'T', 'K', 'k', 'B', 's', 'P', 'p', 'e', 'G', 't', 'r', 'M', 'p', ' ', 'H', 'a'}, 24, 27, 3)
      print(string.format("TEST-3...%s",result))
  
      result = driver({'0', '1', '1', '1', '1', '1', '1', '2', '2', '2', '2', '3', '3', '3', '3', '3', '4', '4', '4', '5', '5', '5', '5', '5', '6', '6', '6', '6', '6', '6', '6', '7', '8', '8', '8', '9', '9'}, 33, 34, 0)
      print(string.format("TEST-4...%s",result))
  
      result = driver({'X', 'B', 'E', 'v', 'K', 't', 'k', 'K', 'Q', 's', 'V', 'N', 'l', 'k', 'T', 'N', 'J', 'z', 'f', 'p', 'J', 'g', 'S', 'P', 'M', 'b', 'H', 'L', 'v', 'E', 'A', 'n', 'D', 'U', 'c', 's', 'M', 'Q', 'P', 'g', 'g', ' '}, 26, 27, 1)
      print(string.format("TEST-5...%s",result))
  
  end
  
  main()
question_info.entry_cls_name: Solution
question_info.test_list: [{"idx": 0, "outputs": 0, "inputs": {"str": ["F", "F", "J", "K", "K", "L", "P", "S", "T", "V", "W", "Y", "b", "d", "j", "l", "t", "u", "x", "y"], "l": 11, "h": 11}}, {"idx": 1, "outputs": 3, "inputs": {"str": ["0", "1", "8", "8", "8", "4", "4", "3", "9", "6", "5", "2", "8", "2", "0", "2", "6", "0", "7", "7", "3", "2", "4", "5", "9", "7", "2", "4", "1", "8", "7", "9", "8", "0", "8", "5", "4", "2", "3"], "l": 19, "h": 22}}, {"idx": 2, "outputs": 0, "inputs": {"str": ["1"], "l": 0, "h": 0}}, {"idx": 3, "outputs": 3, "inputs": {"str": ["g", "y", "r", "M", "v", "z", " ", "k", "S", "P", "x", "p", "E", "z", "T", "K", "k", "B", "s", "P", "p", "e", "G", "t", "r", "M", "p", " ", "H", "a"], "l": 24, "h": 27}}, {"idx": 4, "outputs": 0, "inputs": {"str": ["0", "1", "1", "1", "1", "1", "1", "2", "2", "2", "2", "3", "3", "3", "3", "3", "4", "4", "4", "5", "5", "5", "5", "5", "6", "6", "6", "6", "6", "6", "6", "7", "8", "8", "8", "9", "9"], "l": 33, "h": 34}}, {"idx": 5, "outputs": 1, "inputs": {"str": ["X", "B", "E", "v", "K", "t", "k", "K", "Q", "s", "V", "N", "l", "k", "T", "N", "J", "z", "f", "p", "J", "g", "S", "P", "M", "b", "H", "L", "v", "E", "A", "n", "D", "U", "c", "s", "M", "Q", "P", "g", "g", " "], "l": 26, "h": 27}}]
question_info.extension: lua
question_info.entry_fn_name: dynamic_programming_set_28_minimum_insertions_to_form_a_palindrome
question_info.test_case_ids: 0 1 2 3 4 5
question_info.commands: lua __FILENAME__