Form a Palindrome Efficient Code
In this class, We discuss Form a Palindrome Efficient Code.
The reader can prepare a competitive coding course to crack product development companies. Click Here.
The reader should have basic coding skills to prepare for competitive coding.
Take our placement training course for basic coding. Click Here.
Question:
Given a string S.
Find the minimum number of characters required to make the string a palindrome.
Example:
Input: abcd
abcdcba
we added cba to make the strings palindrome.
Output: 3
Time complexity: O(n^2)
Space complexity: O(n^2)
Logic:
First, we discuss the logic using recursive functions.
The time complexity will be O(2^n) using the recursive functions.
To reduce the time complexity, we use dynamic programming.
The complete explanation is provided in the video.
Code:
class Solution:
def Min(self,a, b):
return min(a, b)
def findMinInsertionsDP(self,str1, n):
table = [[0 for i in range(n)]
for i in range(n)]
l, h, gap = 0, 0, 0
for gap in range(1, n):
l = 0
for h in range(gap, n):
if str1[l] == str1[h]:
table[l][h] = table[l + 1][h – 1]
else:
table[l][h] = (self.Min(table[l][h – 1],
table[l + 1][h]) + 1)
l += 1
return table[0][n – 1];
def countMin(self, Str):
length=len(Str)
return self.findMinInsertionsDP(Str,length)
s = input()
ob=Solution()
z=ob.countMin(s)
print(z)