class Solution {
public:
	int minInsertions(string s) {
		if (s.length() == 1) return 0;
		else {    
			string s2 = s;
			reverse(s2.begin(), s2.end());

			int len = s.length(), len2 = s2.length();
			
			//////////////////here/////////////////////
			int table[2][len2 + 1];
			memset(table[0], 0, sizeof(int) * (len2 + 1));
			table[1][0] = 0;
			//////////////////or////////////////////////
			// vector<vector<int>> table(2, vector<int>(len2 + 1, 0));
			////////////////////////////////////////////
			
			int ans = 0;

			for (int i = 1; i <= len; i++) {
				for (int j = 1; j <= len2; j++) {
					table[i % 2][j] = (s[i - 1] == s2[j - 1] ? table[(i - 1) % 2][j - 1] + 1 : max(table[(i -1) % 2][j], table[i % 2][j - 1]));
					ans = max(ans, j == len2 ? table[i % 2][j]*2 - 1 : table[i % 2][j]*2);
				}
				len2--;
			}

			return len - ans;
		}
	}
};