https://community.topcoder.com/stat?c=problem_statement&pm=1861&rd=4630

ShortPalindromes.cc

#include<string>
#include<iostream>
#include<vector>

using namespace std;

class ShortPalindromes{
public:
	
	string solve(const string & s, int i, int j, 
				 vector<vector<string>> &  mem){
				 
		if(i>j) return "";
		if(i==j) return mem[i][j] = s[i];
		if(mem[i][j] != "") return mem[i][j];
		
		string res;
		string prefix = s[j] + solve(s, i, j-1, mem) + s[j];
		string suffix = s[i] + solve(s, i+1, j, mem) + s[i];
		
		if(prefix.size() != suffix.size()){
			if(prefix.size() < suffix.size()) res = prefix;
			else res = suffix;
		}
		else{
			if(prefix < suffix) res = prefix;
			else res = suffix;
		}
		if(s[i] == s[j]) {
			res = s[i] + solve(s, i+1, j-1, mem) + s[j];
		}
		
		
		return mem[i][j] = res;
	}
	
	string shortest(const string & base){	
		int n = base.size();
		vector<vector<string>> mem(n, vector<string>(n, ""));
		return solve(base, 0, base.size()-1, mem);
	}
};