Leetcode Problem 2430. Maximum Deletions on a String

2430. Maximum Deletions on a String

Leetcode Solutions

Dynamic Programming Approach

  1. Initialize a DP array dp of length n (where n is the length of the string s) with all elements set to 1.
  2. Iterate over the string s in reverse, starting from the second last character to the first.
  3. For each position i, iterate over all possible lengths j such that i + 2*j <= n.
  4. For each length j, check if s[i:i+j] is equal to s[i+j:i+2*j].
  5. If they are equal, update dp[i] to be the maximum of dp[i] and dp[i+j] + 1.
  6. After the iterations, return dp[0] as the result.
UML Thumbnail

Recursive Approach with Memoization

Ask Question

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

Suggested Answer

Answer
Full Screen
Copy Answer Code
Loading...