How long does it take to paint a stick?
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