1312. Minimum Insertion Steps to Make a String Palindrome

Problem Statement

Minimum Insertion Steps to Make a String Palindrome - LeetCode

Pattern:

---

Solution

Integer[][] cache;
 
/// return smallest uncommon subsequence
public int dp (char[] s, int start, int end) {
	if(start <= end) return 0;
	if(cache[start][end] != null) return cache[start][end];
	
	if(s[start] == s[end])
		return cache[start][end] = dp(s, start+1, end-1);
	
	return cache[start][end] = 
		1 + Math.min(dp(s, start+1, end), dp(s, start, end-1));
}
 
public int minInsertions(String s) {
	int n = s.length();
	cache = new Integer[n+1][n+1];
	return dp(s.toCharArray(), 0, n-1);
}

TC : $O(n^2)$ SC : $O(n^2)$

Notes

• Much like 1143. Longest Common Subsequence you simply have to return Smallest Uncommon Subsequence
• The logic is, for every uncommnon letter, you can insert another, to equalise it.