cyberangles blog

Minimum number of deletions to make a string palindrome | Set 2

In the world of string manipulation and algorithms, one common problem is determining the minimum number of deletions required to transform a given string into a palindrome. A palindrome is a string that reads the same forwards and backwards, such as "radar" or "level". Solving this problem efficiently can be crucial in various applications, such as data compression, text processing, and genetic sequence analysis.

In a previous post (Set 1), we might have explored a different approach. In this post (Set 2), we will delve deeper into a more optimized way to solve this problem using dynamic programming. This method offers better time complexity and can handle larger input strings more effectively.

2026-07

Table of Contents#

  1. Problem Statement
  2. Understanding the Approach
  3. Dynamic Programming Solution
    • Algorithm Explanation
    • Python Code Example
    • Complexity Analysis
  4. Common Practices and Best Practices
  5. Example Usage
  6. Conclusion
  7. References

Problem Statement#

Given a string s, the goal is to find the minimum number of character deletions needed to convert the string into a palindrome. For example, if the input string is "abcba", it is already a palindrome, so the minimum number of deletions is 0. If the input string is "abcd", the minimum number of deletions is 3, as we can delete any three characters to get a single - character palindrome.

Understanding the Approach#

The key idea behind solving this problem is to use the concept of the Longest Common Subsequence (LCS). We know that if we reverse the given string s to get s_reversed, the length of the LCS between s and s_reversed represents the longest palindromic subsequence of the original string s.

The minimum number of deletions required to make the string a palindrome is equal to the length of the string minus the length of its longest palindromic subsequence. This is because the longest palindromic subsequence is the part of the string that is already "palindrome - like", and the remaining characters need to be deleted.

Dynamic Programming Solution#

Algorithm Explanation#

  1. Reverse the String: First, reverse the input string s to get s_reversed.
  2. Find the LCS: Use a dynamic programming approach to find the length of the LCS between s and s_reversed.
    • Create a two - dimensional array dp of size (n + 1) x (n+ 1), where n is the length of the string s. dp[i][j] will store the length of the LCS of the first i characters of s and the first j characters of s_reversed.
    • Initialize dp[0][j] = 0 and dp[i][0]=0 for all i and j from 0 to n.
    • For i from 1 to n and j from 1 to n:
      • If s[i - 1]==s_reversed[j - 1], then dp[i][j]=dp[i - 1][j - 1]+1.
      • Otherwise, dp[i][j]=max(dp[i - 1][j], dp[i][j - 1]).
  3. Calculate the Minimum Deletions: The minimum number of deletions is n - dp[n][n], where n is the length of the string s.

Python Code Example#

def min_deletions_to_palindrome(s):
    n = len(s)
    s_reversed = s[::-1]
    dp = [[0] * (n + 1) for _ in range(n + 1)]
 
    for i in range(1, n + 1):
        for j in range(1, n + 1):
            if s[i - 1] == s_reversed[j - 1]:
                dp[i][j] = dp[i - 1][j - 1]+1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
 
    return n - dp[n][n]
 
# Example usage
string = "abcba"
print(min_deletions_to_palindrome(string))

Complexity Analysis#

  • Time Complexity: The time complexity of this algorithm is $O(n^{2})$, where n is the length of the string s. This is because we have two nested loops, each running n times.
  • Space Complexity: The space complexity is also $O(n^{2})$ due to the two - dimensional dp array.

Common Practices and Best Practices#

  • Initialization: Always initialize the dp array properly. In this case, setting dp[0][j] = 0 and dp[i][0]=0 is crucial as it represents the base case when one of the two strings has a length of 0.
  • Code Readability: Use descriptive variable names like s_reversed and dp to make the code easier to understand and maintain.
  • Error Handling: Consider adding input validation to handle edge cases such as empty strings.

Example Usage#

Let's consider a few more examples:

strings = ["abcd", "racecar", "abba"]
for string in strings:
    print(f"String: {string}, Minimum deletions: {min_deletions_to_palindrome(string)}")

For the string "abcd", the minimum number of deletions is 3. For the string "racecar", the minimum number of deletions is 0 as it is already a palindrome. For the string "abba", the minimum number of deletions is also 0.

Conclusion#

In this blog post, we have explored an efficient dynamic programming solution to find the minimum number of deletions required to make a string a palindrome. By using the concept of the Longest Common Subsequence, we were able to reduce the problem to a well - known dynamic programming problem. This approach has a time complexity of $O(n^{2})$, which is a significant improvement over some naive brute - force solutions.

References#