Skip to main content
Talentd

Valid Palindrome III - Solution & Explanation

HardPremiumFree on FleetCodeStringDynamic Programming10 min readAsked at: Amazon, Meta, Tiktok
Practice this problem

Problem Statement

Given a string s and an integer k, return true if s is a k-palindrome.

A string is k-palindrome if it can be transformed into a palindrome by removing at most k characters from it.

 

Example 1:

Input: s = "abcdeca", k = 2
Output: true
Explanation: Remove 'b' and 'e' characters.

Example 2:

Input: s = "abbababa", k = 1
Output: true

 

Constraints:

  • 1 <= s.length <= 1000
  • s consists of only lowercase English letters.
  • 1 <= k <= s.length

Approach Overview

Problem Overview: You are given a string s and an integer k. The task is to determine whether the string can become a palindrome after removing at most k characters. Deletions can occur at any index, but the relative order of remaining characters must stay the same.

The key observation: instead of thinking about which characters to delete, compute how close the string already is to being a palindrome. If the minimum number of deletions required is ≤ k, the answer is true.

Approach 1: Longest Palindromic Subsequence via LCS (O(n²) time, O(n²) space)

A string becomes a palindrome when its longest palindromic subsequence (LPS) is as large as possible. The minimum deletions required is n - LPS. You can compute LPS by finding the Longest Common Subsequence between the string and its reverse. Build a 2D DP table where dp[i][j] represents the LCS length between the first i characters of s and the first j characters of reverse(s). Each state compares characters and extends the subsequence if they match, otherwise it takes the maximum of adjacent states. If n - LPS ≤ k, the string is a valid k‑palindrome. This approach relies on classic dynamic programming over a string.

Approach 2: Direct DP for Minimum Deletions (O(n²) time, O(n²) space)

Instead of computing LPS indirectly, define a DP table dp[i][j] as the minimum deletions needed to make the substring s[i..j] a palindrome. If the characters match (s[i] == s[j]), no deletion is required and you inherit the result from dp[i+1][j-1]. If they differ, delete one side and take the better option: 1 + min(dp[i+1][j], dp[i][j-1]). Fill the table for increasing substring lengths. The final value dp[0][n-1] gives the minimum deletions needed for the entire string. Compare it with k. This formulation is often easier to reason about during interviews because it models the deletion operation directly.

Approach 3: Space-Optimized LCS DP (O(n²) time, O(n) space)

The LCS-based solution only depends on the previous row of the DP table. You can compress the 2D DP into two 1D arrays (or a single rolling array) while iterating through the reversed string. This reduces memory from O(n²) to O(n). The logic remains identical: compute LCS length, derive LPS, then check whether n - LPS ≤ k. Useful when the string length approaches the upper constraints and memory usage matters.

Recommended for interviews: The direct minimum-deletions DP is usually the clearest explanation. It demonstrates understanding of substring DP and state transitions. The LCS-based method is equally valid and often recognized quickly by experienced candidates because LPS = LCS(s, reverse(s)). Showing the brute reasoning about deletions first and then deriving the optimized DP demonstrates strong problem-solving depth.

Solution

The problem requires us to remove at most k characters to make the remaining string a palindrome. This can be transformed into finding the longest palindromic subsequence.

We define f[i][j] as the length of the longest palindromic subsequence in the substring s[i..j]. Initially, we have f[i][i] = 1 for all i, since each single character is a palindrome.

If s[i] = s[j], then we have f[i][j] = f[i+1][j-1] + 2, since we can add both s[i] and s[j] to the longest palindromic subsequence of s[i+1..j-1].

If s[i] neq s[j], then we have f[i][j] = max(f[i+1][j], f[i][j-1]), since we need to remove either s[i] or s[j] to make the remaining substring a palindrome.

Finally, we check whether there exists f[i][j] + k geq n, where n is the length of the string s. If so, it means that we can remove at most k characters to make the remaining string a palindrome.

The time complexity is O(n^2), and the space complexity is O(n^2). Here, n is the length of the string s.

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
LCS-based Longest Palindromic SubsequenceO(n²)O(n²)Clear mathematical formulation using LCS between string and reversed string
Direct DP for Minimum DeletionsO(n²)O(n²)Most intuitive interview explanation based on deleting mismatched characters
Space-Optimized LCS DPO(n²)O(n)When memory constraints matter for large strings

Video Solution

VALID PALINDROME III | LEETCODE 1216 | PYTHON MEMOIZED DFS SOLUTION • Cracking FAANG • 8,971 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Valid Palindrome III easy or hard?
Valid Palindrome III is classified as a hard problem because it requires recognizing the relationship between deletions and the longest palindromic subsequence. Candidates must design a correct dynamic programming state and handle O(n²) transitions.
Valid Palindrome III Python/Java solution
Most implementations build a dynamic programming table of size n × n. Python, Java, C++, Go, TypeScript, and Rust versions follow the same logic: compute the longest palindromic subsequence or minimum deletions and compare the result with k.
How to solve Valid Palindrome III in O(n)?
An exact solution cannot be achieved in O(n) for the general case because the algorithm must evaluate relationships between many character pairs. The best practical solution uses dynamic programming with O(n²) time to compute the longest palindromic subsequence or minimum deletions.
What is the best approach for Valid Palindrome III?
The most common solution uses dynamic programming to compute the Longest Palindromic Subsequence (LPS). If the string length is n and the LPS length is L, then the minimum deletions required is n − L. The string is a valid k‑palindrome if n − L ≤ k. This approach runs in O(n²) time.
Is Valid Palindrome III asked at Google/Amazon/Meta?
Palindrome transformation and subsequence dynamic programming problems appear frequently in interviews at companies like Google, Amazon, and Meta. Variants involving minimum deletions, longest palindromic subsequence, or edit-style DP are common interview patterns.
What data structure is used in Valid Palindrome III?
The primary structure is a 2D dynamic programming table where dp[i][j] stores either the longest common subsequence length or the minimum deletions for substring s[i..j]. The input itself is processed as a string, and optimized versions use rolling arrays.
What is the time complexity of Valid Palindrome III?
The optimal dynamic programming solutions run in O(n²) time because they evaluate all substring pairs or compute LCS between the string and its reverse. Space complexity is typically O(n²), though it can be optimized to O(n) with rolling arrays.

Ready to solve this problem?

Practice Valid Palindrome III with our built-in code editor and test cases.

Practice on FleetCode
Previous

Valid Palindrome II

Next

Valid Palindrome IV