Given a string A, compute the minimum number of characters you need to delete to make resulting string a palindrome.
Examples:
Input : baca Output : 1 Input : cplusplus Output : 6
Below approach will use modified Levensthein distance. We would like to pass to modified Levensthein both original string and its reverse.
C++ Implementation:
#include <algorithm> #include <limits> #include <iostream> #include <string> #include <vector> int getLevenstein(std::string const &input, std::string const &revInput, std::vector<std::vector < int>> &cache) { for (int i = 1; i <= input.size(); ++i) { for (int j = 1; j <= input.size(); ++j) { if (input[i - 1] == revInput[j - 1]) { cache[i][j] = cache[i - 1][j - 1]; } else { cache[i][j] = 1 + std::min({ cache[i - 1][j], cache[i][j - 1] }); } } } /*Go from bottom left to top right and find the minimum*/ int res = std::numeric_limits<int>::max(); for (int i = input.size(), j = 0; i >= 0; --i, ++j) { res = std::min(res, cache[i][j]); if (i < input.size()) { res = std::min(res, cache[i + 1][j]); } if (i > 0) { res = std::min(res, cache[i - 1][j]); } } return res; } int main() { std::string input("cplusplus"); //Prepare cache std::vector<std::vector < int>> cache(input.size() + 1, std::vector<int> (input.size() + 1, -1)); for (int i = 0; i <= input.size(); ++i) { cache[0][i] = i; cache[i][0] = i; } std::string reversed(input.rbegin(), input.rend()); std::cout << "To make it palindrome, " << getLevenstein(input, reversed, cache) << " characters need to be deleted" << std::endl; }
Output:
To make it palindrome, 6 characters need to be deleted
Time complexity: O(n)
Space complexity: O(n)
Where, n is length of string.
- This code calculates minimum deletions.
- It uses the Levenshtein algorithm.
- It finds the minimum number of characters to delete to make a string a palindrome.
- The main function initializes variables and calls the getLevenstein function.
- The result is printed as the number of characters to be deleted.