Find if a string is k-palindrome using dynamic programming technique

Показать описание

A cool addition to Joey's dynamic programming tutorial in which you need to find if a string is k-palindrome or not.

The statement of this DP problem states the following -

You are provided a string

' a b c e d b c a '

And a variable K = 2

All you need to do is to find out if the string is k-palindrome. A K-palindrome means whether this string can be converted in a palindrome by removing k or less than k characters from it.

So, you can see that if you remove 'e' and 'b' then this string becomes a palindrome hence, this string is a K-Palindrome because the number of removed characters is exactly
equal to the value of k.

This is a very interesting dynamic programming problem which is very similar to the minimum edit distance problem.
I have already made a video on the minimum edit distance problem in which I have solved it using the dynamic programming technique.

To get a better hold of the problem I recommend you to watch it first. Here is the link below -

Рекомендации по теме

Комментарии

• 🙏🙏It was fabulous . just provide 👍👍exact clarity . 😍😍what I was👍👍 looking for 👌👌

computerlearningbyargusaca

Thanks for breaking down these DP problems in ways that make them much easier to understand.

chrisogonas

wao you acttually explain everything very very detailed, I have never seen that explanation before, they just initialize the table with first row and column being zero and give me the formula, I don't understand what they do and how the logic work but you actually help me understand everything in that.Thank you sir!!

ucanhly

12:11 how come the minimum value is 2 instead of 1 ? are we only considering the one row back and one column back cells ? what about the diagonal previous cell one row and one column back cell ?

joydeeprony

Great explanation, One doubt? Will it always be the case that final value is even? How can we visualize that?

SHUBHAMKUMAR-yyto

What if we simply calculate longest palindromic subsequence length of given string and check if (given string length - LPS) <= k?
Do you think it will work?

ravitiwari

Btw are u a working professional in any software company?

ayushmishra

Find if a string is k-palindrome using dynamic programming technique

Check if a String Contains all Binary Codes of Size K - Leetcode 1461 - Python

Find if one string is a rotation of another string

Check if a string is a substring of another | GeeksforGeeks

How to check if a string is a palindrome or not? An Optimised Approach

Given two strings, find if first string is a subsequence of second

Given two strings, find if first string is a subsequence of second | GeeksforGeeks

Find the Index of the First Occurrence in a String - Leetcode 28 - Python

Check If A String Is A Palindrome | C Programming Example

DSA Anagrams Challenge | Check if Two Strings Are Anagrams using Python

C++ program to check if a string is unique or not

Check if Substring is Present in a Given String - Java Interview Question

Method to find whether a String belongs to a Grammar or not

Check If A String Is A Palindrome | Python Example

Check If A String Is A Palindrome | C++ Example

Java Program to check given String is Panagram or not?

Find All Anagrams in a String - Leetcode 438 - Python

Frequently Asked Python Program 24:Check if a string contains any special character

Palindrome | Program to check if a string is Palindrome | Java

JavaScript String Contains: How to check a string exists in another

Check String Is Palindrome Or Not

How to Identify a Guitar String

String Interleaving Dynamic Programming

Check If String Contains Any Letters from Alphabet in Python (Example) | any() & isalpha() Funct...

Python program to check whether a string is palindrome or not #shorts #datascience