Solving "string reduction" challenge

Question

I have seen various discussions and code attempts at solving the "String reduction" problem from interviewstreet.com, but none of them does it via dynamic programming.

Listed under the Dynamic Programming section, the problem is described as follows:

Given a string consisting of a,b and c's, we can perform the following operation: 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?

The problem can be solved using exhaustive brute-force search, effectively creating a tree of all possible substitutions:

// this is more or less pseudo code from my head
int GetMinLength(string s)
{
    // solve edge cases
    if (s.Length == 1) return 1;
    if (s.Length == 2) return ReduceIfPossible(s);

    // recursive brute force
    int min = s.Length;
    for (int i = 0; i<s.Length-1; i++)
    {
        if (s[i] != s[i+1])
        {
            var next = GetMinLength(
                  s.Substring(0, i) + 
                  Reduce(s[i], s[i + 1]) +
                  s.Substring(i + 2)
                  );

            if (next < min) min = next;
        }
    }
}

This obviously fails for larger N (N <= 100), so I am trying to break it into smaller subproblems, memoize them, and merge results.

The problem is that I cannot determine the state which would have "optimal substructure", needed to apply dynamic programming (or in other words to "merge" results from sub-problems). Minimizing a part of the string doesn't guarantee that the final string will really be the smallest solution.

What would be the subproblem "state" in this case, which could be merged towards the final solution?

Answer 1

What makes this tricky is that you need to treat this as 2 dynamic programming problems in a row.

1. Build up a table of, by character you wind up with, by start position, all of the possible end positions that are a block that can be reduced to that character.
2. The smallest length that the final i characters of the string can be reduced to. (The table that you built in step 1 can be used to recursively reduce this problem to already solved subproblems.)

The second provides your answer. It is much more straightforward if you have already solved the first.

Answer 2

Spoiler Alert code:

public static int findMinReduction(String line){
    //Pseudocode:
    //Count the number of occurences of each letter in the input string.
    //If two of these counts are 0, then return string.length
    //Else if (all counts are even) or (all counts are odd), then return 2
    //Else, then return 1

    int len = line.length();
    String a_reduce = line.replaceAll("c", "").replaceAll("b", "");
    String b_reduce = line.replaceAll("a", "").replaceAll("c", "");
    String c_reduce = line.replaceAll("a", "").replaceAll("b", "");

    int a_occurances = a_reduce.length();
    int b_occurances = b_reduce.length();
    int c_occurances = c_reduce.length();

    if ((a_occurances == b_occurances && a_occurances == 0) || 
       (a_occurances == c_occurances && a_occurances == 0) || 
       (b_occurances == c_occurances && b_occurances == 0)){
        return len;
    }
    else{
        if (a_occurances % 2 == 0 && 
            b_occurances % 2 == 0 && 
            c_occurances % 2 == 0){
            return 2;
        }
        if (a_occurances % 2 != 0 
            && b_occurances % 2 != 0 && 
            c_occurances % 2 != 0){
            return 2;
        }
    }
    return 1;
}

Complexity:

This is an O(n) time complexity operation, as the input size increases, the amount of work to be done is linear with the size of the input. Which is lightning quick, we can process for megabyte sized strings and still process them in fractions of a second.

Algorithm found here with full analysis of why this algorithm works:

stumped on a Java interview, need some hints