Techie Delight
Coding made easy
Given a string, find minimum number of deletions required to convert it into a palindrome.
For example, consider the string ACBCDBAA. The minimum number of deletions required are 3.
A C B C D B A A or A C B C D B A A —> A B C B A
The idea is to use recursion to solve this problem. The idea is compare the last character of the string X[i..j] with its first character. There are two possibilities –
1. If the last character of the string is same as the first character, no deletion is needed and we recur for the remaining substring X[i+1, j-1]
2. If last character of string is different from the first character, then we return one plus minimum of the two values we get by
This yields the below recursive relation –
Below solution finds the minimum number of deletions required to convert a sequence X into a palindrome recursively by using above relations.
C++
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
|
#include <iostream>
#include <string>
using namespace std;
// Function to find out the minimum number of deletions required to
// convert a given string X[i..j] into a palindrome
int minDeletions(string X, int i, int j)
{
// base condition
if (i >= j)
return 0;
// if last character of the string is same as the first character
if (X[i] == X[j])
return minDeletions(X, i + 1, j – 1);
// else if last character of string is different to the first character
// 1. Remove last character & recur for the remaining substring
// 2. Remove first character & recur for the remaining substring
// return 1 (for remove operation) + minimum of the two values
return 1 + min (minDeletions(X, i, j – 1), minDeletions(X, i + 1, j));
}
int main()
{
string X = “ACBCDBAA”;
int n = X.length();
cout << “The minimum number of deletions required are “ <<
minDeletions(X, 0, n – 1);
return 0;
}
|
Output:
The minimum number of deletions required are 3
Java
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
|
class Main
{
// Function to find out the minimum number of deletions required to
// convert a given String X[i..j] into a palindrome
public static int minDeletions(String X, int i, int j)
{
// base condition
if (i >= j) {
return 0;
}
// if last character of the String is same as the first character
if (X.charAt(i) == X.charAt(j)) {
return minDeletions(X, i + 1, j – 1);
}
// else if last character of String is different to the first character
// 1. Remove last character & recur for the remaining substring
// 2. Remove first character & recur for the remaining substring
// return 1 (for remove operation) + minimum of the two values
return 1 + Math.min(minDeletions(X, i, j – 1), minDeletions(X, i + 1, j));
}
public static void main(String[] args)
{
String X = “ACBCDBAA”;
int n = X.length();
System.out.print(“The minimum number of deletions required are “ +
minDeletions(X, 0, n – 1));
}
}
|
Output:
The minimum number of deletions required are 3
Python
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
|
def minDeletions(X, i, j):
# base condition
if i >= j:
return 0
# if last character of the is same as the first character
if X[i] == X[j]:
return minDeletions(X, i + 1, j – 1)
# else if last character of is different to the first character
# 1. Remove last character & recur for the remaining substring
# 2. Remove first character & recur for the remaining substring
# return 1 (for remove operation) + minimum of the two values
return 1 + min(minDeletions(X, i, j – 1), minDeletions(X, i + 1, j))
if __name__ == ‘__main__’:
X = “ACBCDBAA”
n = len(X)
print(“The minimum number of deletions required are”, minDeletions(X, 0, n – 1))
|
Output:
The minimum number of deletions required are 3
Download Run Code
Output:
The minimum number of deletions required are 3
Download Run Code
Output:
The minimum number of deletions required are 3
Download Run Code
Output:
The minimum number of deletions required are 3
The worst case time complexity of above solution is exponential O(2n) and auxiliary space used by the program is O(1). The worst case happens when there is no repeated character present in X and each recursive call will end up in two recursive calls.
The problem has an optimal substructure. We have seen that the problem can be broken down into smaller subproblems which can further be broken down into yet smaller subproblems, and so on. The problem also exhibits overlapping subproblems we will end up solving the same subproblem over and over again. Let us consider recursion tree for sequence of length 6 having all distinct characters (say ABCDEF).
As we can see, the same sub-problems (highlighted in same color) are getting computed again and again. We know that problems having optimal substructure and overlapping subproblems can be solved by dynamic programming, in which subproblem solutions are Memoized rather than computed again and again. This is illustrated below –
C++
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
|
#include <iostream>
#include <unordered_map>
#include <string>
using namespace std;
// Function to find out the minimum number of deletions required to
// convert a given string X[i..j] into a palindrome
int minDeletions(string X, int i, int j, auto &lookup)
{
// base condition
if (i >= j)
return 0;
// construct an unique map key from dynamic elements of the input
string key = to_string(i) + “|” + to_string(j);
// if sub-problem is seen for the first time, solve it and
// store its result in a map
if (lookup.find(key) == lookup.end())
{
// if last character of the string is same as the first character
if (X[i] == X[j])
lookup[key] = minDeletions(X, i + 1, j – 1, lookup);
else
// if last character of string is different to the first character
// 1. Remove last character & recur for the remaining substring
// 2. Remove first character & recur for the remaining substring
// return 1 (for remove operation) + minimum of the two values
lookup[key] = 1 + min (minDeletions(X, i, j – 1, lookup),
minDeletions(X, i + 1, j, lookup));
}
// return the subproblem solution from the map
return lookup[key];
}
int main()
{
string X = “ACBCDBAA”;
int n = X.length();
// create a map to store solutions of subproblems
unordered_map<string, int> lookup;
cout << “The minimum number of deletions required are “ <<
minDeletions(X, 0, n – 1, lookup);
return 0;
}
|
Output:
The minimum number of deletions required are 3
Java
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
|
import java.util.HashMap;
import java.util.Map;
class Main
{
// Function to find out the minimum number of deletions required to
// convert a given String X[i..j] into a palindrome
public static int minDeletions(String X, int i, int j, Map<String, Integer> lookup)
{
// base condition
if (i >= j) {
return 0;
}
// construct an unique map key from dynamic elements of the input
String key = i + “|” + j;
// if sub-problem is seen for the first time, solve it and
// store its result in a map
if (!lookup.containsKey(key))
{
// if last character of the String is same as the first character
if (X.charAt(i) == X.charAt(j)) {
lookup.put(key, minDeletions(X, i + 1, j – 1, lookup));
}
else {
// if last character of String is different to the first character
// 1. Remove last character & recur for the remaining substring
// 2. Remove first character & recur for the remaining substring
// return 1 (for remove operation) + minimum of the two values
int res = 1 + Math.min(minDeletions(X, i, j – 1, lookup),
minDeletions(X, i + 1, j, lookup));
lookup.put(key, res);
}
}
// return the subproblem solution from the map
return lookup.get(key);
}
public static void main(String[] args)
{
String X = “ACBCDBAA”;
int n = X.length();
// create a map to store solutions of subproblems
Map<String, Integer> lookup = new HashMap<>();
System.out.print(“The minimum number of deletions required are “ +
minDeletions(X, 0, n – 1, lookup));
}
}
|
Output:
The minimum number of deletions required are 3
Python
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
|
# Function to find out the minimum number of deletions required to
# convert a given X[i..j] into a palindrome
def minDeletions(X, i, j, lookup):
# base condition
if i >= j:
return 0
# construct an unique dict key from dynamic elements of the input
key = (i, j)
# if sub-problem is seen for the first time, solve it and
# store its result in a dict
if key not in lookup:
# if last character of the is same as the first character
if X[i] == X[j]:
lookup[key] = minDeletions(X, i + 1, j – 1, lookup)
else:
# if last character of is different to the first character
# 1. Remove last character & recur for the remaining substring
# 2. Remove first character & recur for the remaining substring
# return 1 (for remove operation) + minimum of the two values
res = 1 + min(minDeletions(X, i, j – 1, lookup),
minDeletions(X, i + 1, j, lookup))
lookup[key] = res
# return the subproblem solution from the dictionary
return lookup[key]
if __name__ == ‘__main__’:
X = “ACBCDBAA”
n = len(X)
# create a dictionary to store solutions of subproblems
lookup = {}
print(“The minimum number of deletions required are”, minDeletions(X, 0, n – 1, lookup))
|
Output:
The minimum number of deletions required are 3
Download Run Code
Output:
The minimum number of deletions required are 3
Download Run Code
Output:
The minimum number of deletions required are 3
Download Run Code
Output:
The minimum number of deletions required are 3
The time complexity of above solution is O(n2) and auxiliary space used by the program is O(n2).
This problem is also a classic variation of Longest Common Subsequence (LCS) problem. The idea is to find the Longest Palindromic Subsequence of given string. Then the minimum number of deletions required will be size of the string minus size of the longest palindromic subsequence. We can easily find the longest palindromic Subsequence by taking Longest Common Subsequence of a given string with its reverse i.e. call LCS(X, reverse(X)).
C++
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
|
#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
// Function to find out the minimum number of deletions required to
// convert a given string X[0..n-1] into a palindrome
int minDeletions(string X, int n)
{
// string Y is reverse of X
string Y = X;
reverse(Y.begin(), Y.end());
// lookup[i][j] stores the length of LCS of substring
// X[0..i-1], Y[0..j-1]
int lookup[n + 1][n + 1];
// first column of the lookup table will be all 0
for (int i = 0; i <= n; i++)
lookup[i][0] = 0;
// first row of the lookup table will be all 0
for (int j = 0; j <= n; j++)
lookup[0][j] = 0;
// fill the lookup table in bottom-up manner
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
{
// if current character of X and Y matches
if (X[i – 1] == Y[j – 1])
lookup[i][j] = lookup[i – 1][j – 1] + 1;
// else if current character of X and Y don’t match
else
lookup[i][j] = max(lookup[i – 1][j], lookup[i][j – 1]);
}
}
// Now lookup[n][n] contains the size of the Longest Palindromic Subsequence
// The minimum number of deletions required will be size of the string
// minus size of the Palindromic Subsequence
return n – lookup[n][n];
}
int main()
{
string X = “ACBCDBAA”;
int n = X.length();
cout << “The minimum number of deletions required are “ <<
minDeletions(X, n);
return 0;
}
|
Output:
The minimum number of deletions required are 3
Java
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
|
class Main
{
// Function to find out the minimum number of deletions required to
// convert a given String X[0..n-1] into a palindrome
public static int minDeletions(String X, int n)
{
// String Y is reverse of X
String Y = new StringBuilder(X).reverse().toString();
// lookup[i][j] stores the length of LCS of substring
// X[0..i-1], Y[0..j-1]
int[][] lookup = new int[n + 1][n + 1];
// fill the lookup table in bottom-up manner
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++) {
// if current character of X and Y matches
if (X.charAt(i – 1) == Y.charAt(j – 1)) {
lookup[i][j] = lookup[i – 1][j – 1] + 1;
}
// else if current character of X and Y don’t match
else {
lookup[i][j] = Math.max(lookup[i – 1][j], lookup[i][j – 1]);
}
}
}
// Now lookup[n][n] contains the size of the Longest Palindromic Subsequence
// The minimum number of deletions required will be size of the String
// minus size of the Palindromic Subsequence
return n – lookup[n][n];
}
public static void main(String[] args)
{
String X = “ACBCDBAA”;
int n = X.length();
System.out.print(“The minimum number of deletions required are “ +
minDeletions(X, n));
}
}
|
Output:
The minimum number of deletions required are 3
Python
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
|
# Function to find out the minimum number of deletions required to
# convert a given X[0..n-1] into a palindrome
def minDeletions(X, n):
# Y is reverse of X
Y = X[::–1]
# lookup[i][j] stores the length of LCS of substring
# X[0..i-1], Y[0..j-1]
lookup = [[0 for x in range(n + 1)] for y in range((n + 1))]
# fill the lookup table in bottom-up manner
for i in range(1, n + 1):
for j in range(1, n + 1):
# if current character of X and Y matches
if X[i – 1] == Y[j – 1]:
lookup[i][j] = lookup[i – 1][j – 1] + 1
# else if current character of X and Y don’t match
else:
lookup[i][j] = max(lookup[i – 1][j], lookup[i][j – 1])
# Now lookup[n][n] contains the size of the Longest Palindromic Subsequence
# The minimum number of deletions required will be size of the String
# minus size of the Palindromic Subsequence
return n – lookup[n][n]
if __name__ == ‘__main__’:
X = “ACBCDBAA”
n = len(X)
print(“The minimum number of deletions required are”, minDeletions(X, n))
|
Output:
The minimum number of deletions required are 3
Download Run Code
Output:
The minimum number of deletions required are 3
Download Run Code
Output:
The minimum number of deletions required are 3
Download Run Code
Output:
The minimum number of deletions required are 3
The time complexity of above solution is O(n2) and auxiliary space used by the program is O(n2).
Exercise: Write bottom-up solution for above recursive top-down version.
(40 votes, average: 5.00 out of 5)
Loading…
Thanks for reading.
Guess there’s a typo in the explanation of the recurrence relation. It should be T[i..j] = 1 + min ( T[i-1..j], T[i+1…j] ).
Thanks a lot for bringing this to our notice. We have updated the article. Happy coding 🙂
This will result in incorrect output for, case when input is ACBCDBA, per your program output is 4, it should be 2.
Though idea is good, you should be checking for next and previous character at every step before incrementing the flag.
another simple idea can find LCS of string and its reverse string.
and output s.length()-LCSvalue
I think you mean to say longest palindromic subsequence not the substring.
Thanks a lot for bringing this to our notice. We have updated the typo. Happy coding 🙂
The space complexity would be O(N) if we use unordered map.
O(N^2) is a mistake I guess admin ?