Statistics

Problem Statement for "LineOff"

Problem Statement

You are given a set of colored points on a straight line.

You play a game with these points. The game is a sequence of moves. In each move you have to erase two points that are adjacent and share the same color. (Two points are adjacent if there is no other point between them. Distances don't matter.)

You are given the String points. Each character of points describes the color of one point, in the order in which they are arranged on the line at the beginning of the game. (Different letters represent different colors.) Compute and return the maximum number of moves you can make.

Definition

Class:
LineOff
Method:
movesToDo
Parameters:
String
Returns:
int
Method signature:
int movesToDo(String points)
(be sure your method is public)

Constraints

  • points will contain between 1 and 50 characters, inclusive.
  • Each character in points will be a lowercase English letter ('a'-'z').

Examples

  1. "abba"

    Returns: 2

    The only valid first move is to erase the two points of color 'b'. After that move the points of color 'a' are now adjacent and they can be removed in our second move.

  2. "zwwwzffw"

    Returns: 2

    You can remove two 'w' points and two 'f' points with your first two moves. After that the remaining points on the line will be arranged as follows: "zwzw". In this situation you don't have any adjacent points that share the same color, so there are no more moves.

  3. "rrrrrrr"

    Returns: 3

    With an odd number of points, at least one of them will have no pair.

  4. "dfghj"

    Returns: 0

    All colors are different so no points can be removed.

  5. "wasitacarooracatisaw"

    Returns: 10

  6. "abcdefghijklmnopqrstuvxyzzyxvutsrqponmlkjihgfedcba"

    Returns: 25

    max test specific move order

  7. "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"

    Returns: 25

    max test any order

  8. "cacaabaabcaacbbaacbcaaabcaaabaaabbcbcbaaabaaccaabb"

    Returns: 17

  9. "bcedaeacabadccadbadbbbadddebdbcbcbdbaccbaebeccccce"

    Returns: 6

  10. "zzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz"

    Returns: 24

  11. "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabbbbb"

    Returns: 24

  12. "bbbbbdcccccccccaacccccbbbbaaaaaadddddddddaaaaaaaaa"

    Returns: 24

  13. "baabbbbbbaaaababababbbbaabbaaaababababaaabaababbaa"

    Returns: 19

  14. "aabbacccbaababcccbbccbcbacccbbcacbcbcabbabacccbbca"

    Returns: 18

  15. "cdbebdcaeacdeaeeccbecbeadcddcdeadbbaccbbeaaeceedeb"

    Returns: 11

  16. "aaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbb"

    Returns: 24

  17. "aaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbb"

    Returns: 25

  18. "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbb"

    Returns: 24

  19. "aaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb"

    Returns: 24

  20. "mmmmmmmmmmmmmmmmmmmmecdeacbedbcdaaebecbeqqqqqqqqqq"

    Returns: 16

  21. "ababababababababababababababababababababababababab"

    Returns: 0

  22. "bbbbaaaaaaabbbbbbbbbaaaaaaaaaabbbbbbbbaaaaaaaaaabb"

    Returns: 24

  23. "cccccccccccccaaaaaaaaacccccbaaaaaaaabbbbbbbbbbabbb"

    Returns: 22

  24. "ddddddddddbbbbccccbbbbbbbbbbbbbaaaaaaabbbbbbbccccc"

    Returns: 23

  25. "bbdbcbgggrrgbcaabd"

    Returns: 9

  26. "tuvxyzzyxlmnopqrssrqponmlvuabcdefghijkkjihgfedcbat"

    Returns: 25

  27. "k"

    Returns: 0

    min test

  28. "amanaplanaccanalpanama"

    Returns: 11

  29. "noxinnixonmadam"

    Returns: 5

  30. "faaaccccf"

    Returns: 3

  31. "ntzlylvwulbdkcdppgykichjtpukfnlxfcevkjezqsme"

    Returns: 1

  32. "wimliygnfddfeswmxxuvhnqvjzgkpdzf"

    Returns: 3

  33. "ykzeqjjpehsgiqvyezbqwnpyuciolbbloxjxuozsuvqwphl"

    Returns: 4

  34. "mlotftnqrjolvuamahndekfdsqcfvm"

    Returns: 0

  35. "shtmrentgsnddnbttbbbmougguopyypw"

    Returns: 10

  36. "aabbccddeeffgghhiijjkkllmmnnooppqqrrssttuuvvwwxxyy"

    Returns: 25

  37. "aaba"

    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: