Write a method named longestPalindromeSubstring that uses dynamic programming to find and return the longest palindrome substring that occurs in a given string.
A palindrome is a string that is the same forwards as backwards, such as "madam" or "racecar".
For example, if the string is "GABAABBADABA", the longest palindrome substring is "BADAB".
If the string contains multiple palindrome substrings of the same max length, you may return of them.
Any one-letter string is considered a palindrome, so if the string consists of entirely distinct characters, return any one-letter string from it.
If the string is empty, return "".
You may assume that the string's length is 1000 or less.
The key constraint of this problem is that you must solve it using a bottom-up dynamic programming approach.
Do not use recursion.
You are allowed to construct any data structures (array, list, set, map, etc.) necessary to store the data for your dynamic programming algorithm.
You are also allowed to define other "helper" methods if you like.
