How to convert a recursive solution to bottom up or top down solution?
===

I am solving this problem-

> Given a string consisting of a,b and c's, we can take any two adjacent
> distinct characters and replace it with the third character. For
> example, if 'a' and 'c' are adjacent, they can replaced with 'b'. What
> is the smallest string which can result by applying this operation
> repeatedly?

Now I have written the following recursive solution (far from efficient), but want to convert it to either top-down or bottom-up solution. 

**Problem**: I am not able to come up with a tabular structure for memoization. Even though I have to output only the length of resulting string, how can I solve it without actually solving the problem. The strings are getting reduced, so how do I store them?

Any hint for DP solution or Memoization would be great!

    #include <iostream>
    #include <string>
    
    using namespace std;
    
    string reduce(string s)
    {
    	if (s.length() <= 1)
    		return s;
    	if (s.length() == 2){
    		if (s[0] != 'a' && s[1] != 'a')
    			s[0] = 'a';
    		else if (s[0] != 'b' && s[1] != 'b')
    			s[0] = 'b';
    		else if (s[0] != 'c' && s[1] != 'c')
    			s[0] = 'c';
    		s.resize(1);
    		return s;
    	}
    	int k;
    	char c = s[0];
    	string min = s;
    	for (k = 1; k < s.length() && c; ++k)
    		if (s[k] != c)
    			c = 0;
    	if (c)
    		return s;
    
    	for (k = 1; k < s.length(); ++k){
    		string s1 = reduce(s.substr(0, k));
    		string s2 = reduce(s.substr(k));
    
    		if (s1.length() + s2.length() < min.length())
    			min = s1 + s2;
    		if (!s1.empty() && !s2.empty() && s1.back() != s2.front()){
    			if (s1.back() != 'a' && s2.front() != 'a')
    				s1.back() = 'a';
    			else if (s1.back() != 'b' && s2.front() != 'b')
    				s1.back() = 'b';
    			else if (s1.back() != 'c' && s2.front() != 'c')
    				s1.back() = 'c';
    			s1 = reduce(s1 + s2.substr(1));
    			if (s1.length() < min.length())
    				min = s1;
    		}
    
    	}
    	return min;
    }
    
    int main()
    {
        string input;
        cin >> input;
    	cout << reduce(input) << endl;
    	return 0;
    }
