Leetcode Problem 2472. Maximum Number of Non-overlapping Palindrome Substrings

2472. Maximum Number of Non-overlapping Palindrome Substrings

Leetcode Solutions

Dynamic Programming with Palindrome Checking

  1. Create a 2D boolean array dp to store palindrome information such that dp[i][j] is true if s[i...j] is a palindrome.
  2. Initialize dp[i][i] to true for all i (single character is a palindrome).
  3. Set dp[i][i+1] to true if s[i] == s[i+1] for all i (two same characters next to each other are a palindrome).
  4. Fill the rest of dp using dynamic programming. For each length l from 3 to n, check for all i if s[i] == s[i+l-1] and dp[i+1][i+l-2] is true, then set dp[i][i+l-1] to true.
  5. Define a recursive function solve(i) that returns the maximum number of palindromic substrings starting from index i.
  6. In solve(i), if i is at the end of the string, return 0.
  7. If memo[i] is not -1, return memo[i] (use memoization).
  8. Set result to solve(i+1) (skip the current index).
  9. For each j from i+k to n, if dp[i][j-1] is true, set result to the maximum of result and solve(j)+1.
  10. Store result in memo[i] and return it.
  11. Call solve(0) and return its result as the final answer.
UML Thumbnail

Greedy Approach with Center Expansion

Ask Question

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

Suggested Answer

Answer
Full Screen
Copy Answer Code
Loading...