Minimum number of characters need to delete to make resulting string a palindrome

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.

1. This code calculates minimum deletions.
2. It uses the Levenshtein algorithm.
3. It finds the minimum number of characters to delete to make a string a palindrome.
4. The main function initializes variables and calls the getLevenstein function.
5. The result is printed as the number of characters to be deleted.