/
min_del_to make string palindrome.cpp
134 lines (103 loc) Β· 2.71 KB
/
min_del_to make string palindrome.cpp
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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
/*
///////////////////////////////////////////
//Question/Info
Minimum number of deletions to make a string palindrome
Given a string of size βnβ. The task is to remove
or delete the minimum number of characters from
the string so that the resultant string is a palindrome.
Note: The order of characters should be maintained.
Examples :
Input : aebcbda
Output : 2
Remove characters 'e' and 'd'
Resultant string will be 'abcba'
which is a palindromic string
Input : geeksforgeeks
Output : 8
///////////////////////////////////////////
*/
#include <bits/stdc++.h>
using namespace std;
#define int long long int
#define setbits(x) __builtin_popcount(x)
#define pb(x) push_back(x)
#define mp(x,y) make_pair(x,y)
#define eb(x) emplace_back(x)
#define ct(x) cout<<x<<endl;
#define ct2(x,y) cout<<x<<" "<<y<<endl;
#define forn(i,n) for(int i = 0; i < (int)(n); i++)
#define forx(i,x,n) for(int i = x; i < (int)(n); i++)
#define all(v) v.begin(),v.end()
#define fsp(x,y) fixed<<setprecision(y)<<x;
#define PI 3.1415926535897932384626433832795
#define MOD 1000000007 // (1e9+7)
#define pii pair<int,int>
#define pis pair<int,string>
#define vi vector<int>
#define vii vector<pii>
#define mii map<int,int>
// typedef long long int lli;
typedef long double ld;
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
void c_p_c()
{
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
}
// using bottom up dp
int mnds(string a, string b, int la, int lb) {
// NOTE THAT string b IS JUST THE REVERSE OF string a
int dp[la + 1][lb + 1];
forn(i, la + 1) {
forn(j, lb + 1) {
// base case
if (i == 0 or j == 0) {
dp[i][j] = 0;
}
else {
if (a[i - 1] == b[j - 1]) {
dp[i][j] = 1 + dp[i - 1][j - 1];
}
else {
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
}
/*
The q. , is similar to finding length of longest palindrome
subseq, here just delete string length with palin. length,
to get the total insertion/del. required to convert string
to a palindrome string.
*/
/*
SAME APPROACH TO FIND MIN. NUMBER OF INSERTIONS IN STRING
TO GET PALINDROME....
AS NO. OF INSERTION WOULD EQUAL NO. OF DELETION
TO GET PALINDROME.
*/
int kk = la - dp[la][lb]; // we know , la == lb...
return kk;
}
int32_t main() {
///////////
c_p_c();
///////////
// code
/*
int t ; cin >> t; while(t--){}
*/
string a = "abcgba";
int la = a.length();
string b = a;
reverse(all(b));
int lb = b.length();
// dp bottom up
ct(mnds(a , b , la, lb));
// cerr << "time: " << clock() << " ms" << '\n';
return 0;
}