How long does it take to paint a stick? (Based on this Math.SE problem, which also provides some graphics)

I have a stick which looks kinda like this:



I want it to look kinda like this:



I'm not an expert painter, however, so before I start such an ambitious DIY project, I want to make sure that I'm not in over my head.

Your program should tell me how  how many steps are involved in painting this stick.  Each step involves painting a continuous area with a solid color, which covers up previous layers of paint.  For the above example, I could paint the left half blue, the right half red, and then the two separate green areas for a total of 4 steps (the green is not continuously painted).



Here it is in ASCII:

------
bbb---
bbbrrr
bgbrrr
bgbrgr


There are a couple different ways to paint this stick and end up with the same result.  I'm only interested in the time estimate, however, which is four steps.

Goal

Your program should output the minimum number of steps needed to paint a stick with a given color scheme.  The paint scheme will be in the form of a string of characters, while output will be a number. This is code golf.  Shortest program wins.  

Input

Your program will receive the coloring scheme for a stick in the form of a string of letters.  Each unique letter (case sensitive) represents a unique color.

YRYGR

grG

GyRyGyG

pbgbrgrp

hyghgy


Output

These numbers are the least number of steps needed to paint the sticks.

4

3

4

5

4


Explanations

This is how I arrived at the above numbers.  Your program does not need to output this:

 -----
 YYY--
 YRY--
 YRYG-
 YRYGR

 ---
 g--
 gr-
 grG

 -------
 GGGGGGG
 GyyyGGG
 GyRyGGG
 GyRyGyG

 --------
 pppppppp
 pbbbpppp
 pbbbrrrp
 pbgbrrrp
 pbgbrgrp

 ------
 -yyyyy
 -ygggy
 hygggy
 hyghgy


Edit: I'll add more test cases if they prove to be more difficult test cases.
GolfScript, 82 72 67 characters
.,n*{:c,,{[).2$1&lt;*\c&gt;+1$.,,{).2$&lt;\3$&lt;=},,.@&gt;@@&gt;]}%\;{~S)}%$0+0=}:S~

Reasonably fast for a GolfScript program, examples:
&gt; hyghgy
4

&gt; pbgbrgrp
5

The algorithm used works through the colors left-to-right recursively, according to the following statements:

Ignore all parts from the left which already have the required color. Overpainting them again will not provide a better answer.

If the complete stick already has the desired color, return 0 steps as result.

Otherwise, take the target color of the now leftmost part (i.e. the first not in the desired color).

Paint 1 part with the target color and recurse.
Paint 2 parts with this color and recurse.

...

Paint the whole remaining stick with this color and recurse.

Take the minimum of all those numbers and add 1 (for the current step). Return this as the optimal number of steps.


This algorithm works, because the leftmost part has to be painted at one time anyways, so why not do it immediately - in any possible fashion.
.,n*         # prepare the initial situation (target stick, unpainted stick)
             # used n instead of '-' for the unpainted parts, because it is shorter
{            # Define the operator S which does t c S -&gt; n
             #   - t: the desired target colors
             #   - c: the stick as it is colored currently
             #   - n: minimum number of steps required to go from c to t
  :c         # Assign the current configuration to the variable c
  ,,{[       # Map the list [0 1 2 .. L-1]
             # We will build a list of all possible configurations if we paint
             # the stick with the 0th part's color (either 1 or 2 or 3 or ... parts)
    ).       # Increase the number, i.e. we paint 1, 2, 3, ... L parts, copy
    2$1&lt;     # Take the first color of the target configuration
    *        # ...paint as many parts
    \c&gt;+     # ...and keep the rest as with the current stick
    1$       # take the target configuration
             # Top of stack now e.g. reads
             #    h----- hyghgy (for i=0)
             #    hh---- hyghgy (for i=1)
             # Next, we strip the common leading characters from both strings:
    .,,      # Make list [0 1 2 ... L-1]
    {        # Filter {}, all the numbers for which the first j+1 parts are the same
      ).     # incr j
      2$&lt;    # take leftmost j parts of stick A
      \3$&lt;   # take leftmost j parts of stick B
      =      # are they equal?
    },,      # The length of the result is the number of common parts.
    .@&gt;      # cut parts from A
    @@&gt;      # cut parts from B
  ]}%
  \;         # Remove the target from the stack (not needed anymore)               
             # We now have a list of possible paintings where 1, 2, ..., L parts were
             # painted from the left with the same color.
             # All configurations were reduced by the common parts (they won't be
             # painted over anyways)
  {~S)}%     # Call the method S recursively on the previously prepared configurations
  $0+0=      # $0= -&gt; sort and take first, i.e. take the minimum, 0+ is a workaround
             # if the list was empty (i.e. the operator was called with a stick of length 0).
}:S
~            # Execute S