Statistics

Problem Statement for "StripePainter"

Problem Statement

Karel is a frustrated painter who works by day in an electrical repair shop. Inspired by the color-coded bands on resistors, he is painting a series of long, narrow canvases with bold colored stripes. However, Karel is lazy and wants to minimize the number of brush strokes it takes to paint each canvas.

Abbreviating each color to a single uppercase letter, Karel would write the stripe pattern red-green-blue-green-red as "RGBGR" (quotes added for clarity). It would take him three brush strokes to paint this pattern. The first stroke would cover the entire canvas in red (RRRRR). The second stroke would leave a band of red on either side and fill in the rest with green (RGGGR). The final brush stroke would fill in the blue stripe in the center (RGBGR).

Given a stripe pattern stripes as a String, calculate the minimum number of brush strokes required to paint that pattern.

Definition

Class:
StripePainter
Method:
minStrokes
Parameters:
String
Returns:
int
Method signature:
int minStrokes(String stripes)
(be sure your method is public)

Notes

  • The blank canvas is an ugly color and must not show through.

Constraints

  • stripes will contain only uppercase letters ('A'-'Z', inclusive).
  • stripes will contain between 1 and 50 characters, inclusive.

Examples

  1. "RGBGR"

    Returns: 3

    Example from introduction.

  2. "RGRG"

    Returns: 3

    This example cannot be done in two strokes, even though there are only two colors. Suppose you tried to paint both red stripes in one stroke, followed by both green stripes in one stroke. Then the green stroke would cover up the second red stripe. If you tried to paint both green stripes first, followed the red stripes, then the red stroke would cover up the first green stripe.

  3. "ABACADA"

    Returns: 4

    One long stroke in color 'A', followed by one stroke each in colors 'B', 'C', and 'D'.

  4. "AABBCCDDCCBBAABBCCDD"

    Returns: 7

  5. "ABCDEFGHIJKLMNOPQRSTUVWQQQWVUTSRQPONMLKJIHGFEDCBA"

    Returns: 24

    A bunch of nested colors, with a few extra stripes in the middle.

  6. "ABCDEFGHIJKLMNOPQRSTUVWABCDEFGHIJKLMNOPQRSTUVW"

    Returns: 45

    Different colors, almost no sharing possible.

  7. "JJJJJJJJJJJJKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKK"

    Returns: 2

    Two wide stripes.

  8. "ABCDEFGGFEDCBAABCDEFG"

    Returns: 13

    Two different aproaches to sharing that interfere with each other.

  9. "ABCDCBAABCDCBAAAAABCDCBA"

    Returns: 10

    One big background stripe with several independent sets in the middle.

  10. "BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB"

    Returns: 1

  11. "X"

    Returns: 1

  12. "RGBGRB"

    Returns: 4

  13. "ABCDE"

    Returns: 5

  14. "ABCDEFGHIJKLMNOPQRSTUVWXYYXWVUTSRQPONMLKJIHGFEDCBA"

    Returns: 25

  15. "JGXJFGDKGTCVGHJVGHJGDJGHVGHJFDGHJGFGHJ"

    Returns: 26

  16. "ABCDEFGHIJKLMNOPQRSTUVWXYZ"

    Returns: 26

  17. "AEBEACABDABDB"

    Returns: 8

  18. "CGBBCDCGEAGCEEIAABHFCIKEHFBHG"

    Returns: 19

  19. "DBBFKDHEIGKJHGBJFEDCEHJHIGBEB"

    Returns: 21

  20. "DEJJEDAIJHBFCEGHFEADCJAIIGKBF"

    Returns: 21

  21. "DACHIGFHECADGCDFEIEHIDFCEGIIGFCDGDCFIIGCIIDCGFIGHG"

    Returns: 30

  22. "CIBIGBFBCGAEHFHGCFEEGGIGFIBIIAGFHEGBAHIIFIHDGEGIDF"

    Returns: 30

  23. "CAACEBBABCBEBBCACAAEEBBAAEBAAEDCEEEBECAAEAECBCCDEB"

    Returns: 23

  24. "ADAEBCBCACBDEAACAEAEABCDABAABCEEBDDCDDDCBEBABDDDBC"

    Returns: 24

  25. "BECBBDDEEBABDCADEAAEABCACBDBEECDEDEACACCBEDABEDADD"

    Returns: 26

  26. "EBEDBDEAAECDBEAECDBCCDCBCCECACAEDDAAEBCDCCDAAAAEDE"

    Returns: 24

  27. "HAEBDFDFEEFEFBHIGGGBACFEIAFHFABAECBIFFDEAEFHACHCDF"

    Returns: 30

  28. "GDBBKCKABKHJDDJEJHKAIGEKCKGAC"

    Returns: 18

  29. "ABCBADEFED"

    Returns: 6

  30. "EACBDEBCEDFAFACFABAFEACDFCBEDECFEFADAEFE"

    Returns: 24

  31. "BECBBDDEEBABDCADEAAEABCACBDBEECDEDEACACCBEDABEDADD"

    Returns: 26

  32. "BECBBDDEEBABDCADEAAEABCACBDBEECDEDEACACCBEDABEDABB"

    Returns: 26

  33. "ABABABABCDEFGHIJKJHIGFEDABABABABCABABCAAAAABCABAAA"

    Returns: 26

  34. "BECBBDDEEBABDCADEAAEABCACBDBEECDEDEACACCBEDABEBACC"

    Returns: 26

  35. "ABABABABABABABABABABABABABABABABABABABABABABABABAB"

    Returns: 26

  36. "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA"

    Returns: 1

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2024, TopCoder, Inc. All rights reserved.
This problem was used for: