Statistics

Problem Statement for "IdealString"

Problem Statement

An ideal string is a string where the 1-based index of the first occurrence of each letter is equal to the number of occurrences of that letter in the string. For example, the "BAOOOA" is an ideal string (quotes for clarity only). The letter 'B' appears 1 time, and its index is 1. The letter 'A' occurs 2 times and its first index is 2. The letter 'O' occurs 3 times and its first index is 3.

Given an int length, return the lexicographically smallest ideal string of that length containing only uppercase letters ('A'-'Z'). If there are no such ideal strings of that length, return an empty String instead.

Definition

Class:
IdealString
Method:
construct
Parameters:
int
Returns:
String
Method signature:
String construct(int length)
(be sure your method is public)

Notes

  • String A is lexicographically smaller than string B of the same length if it contains a smaller letter at the first position they differ. Letter X is smaller than letter Y if it comes earlier in the alphabet.

Constraints

  • length will be between 1 and 100, inclusive.

Examples

  1. 1

    Returns: "A"

  2. 3

    Returns: "ABB"

  3. 2

    Returns: ""

    There's no way we can construct an ideal string of length 2 - if both its characters are equal, then the number of occurrences (2) and the position of its first occurrence (1) do not match; if they are distinct, then for the second character the number of occurrences (1) and the position of its first occurrence (2) do not match as well.

  4. 4

    Returns: ""

  5. 6

    Returns: "ABCBCC"

    We can permute the last 3 characters in any way, but this way gets us the lexicographically smallest answer.

  6. 7

    Returns: "ABBCCCC"

  7. 5

    Returns: ""

  8. 8

    Returns: ""

  9. 9

    Returns: ""

  10. 10

    Returns: "ABCDBCCDDD"

  11. 11

    Returns: "ABCBDCCDDDD"

  12. 12

    Returns: "ABBCDCCCDDDD"

  13. 13

    Returns: "ABBCCDCCDDDDD"

  14. 14

    Returns: "ABBCCCDCDDDDDD"

  15. 15

    Returns: "ABBCCCCDDDDDDDD"

  16. 16

    Returns: "ABCDBECCDDDEEEEE"

  17. 17

    Returns: "ABCBDECCDDDDEEEEE"

  18. 18

    Returns: "ABBCDECCCDDDDEEEEE"

  19. 19

    Returns: "ABBCDCECCDDDDEEEEEE"

  20. 20

    Returns: "ABBCCDECCDDDDDEEEEEE"

  21. 21

    Returns: "ABBCCDCECDDDDDEEEEEEE"

  22. 22

    Returns: "ABBCCCDECDDDDDDEEEEEEE"

  23. 23

    Returns: "ABBCCCDCEDDDDDDEEEEEEEE"

  24. 24

    Returns: "ABBCCCCDEDDDDDDDEEEEEEEE"

  25. 25

    Returns: "ABBCCCCDDEDDDDDDEEEEEEEEE"

  26. 26

    Returns: "ABBCCCCDDDEDDDDDEEEEEEEEEE"

  27. 27

    Returns: "ABBCCCCDDDDEDDDDEEEEEEEEEEE"

  28. 28

    Returns: "ABBCCCCDDDDDEDDDEEEEEEEEEEEE"

  29. 29

    Returns: "ABBCCCCDDDDDDEDDEEEEEEEEEEEEE"

  30. 30

    Returns: "ABBCCCCDDDDDDDEDEEEEEEEEEEEEEE"

  31. 31

    Returns: "ABBCCCCDDDDDDDDEEEEEEEEEEEEEEEE"

  32. 32

    Returns: "ABBCCCDECFDDDDDDEEEEEEEFFFFFFFFF"

  33. 33

    Returns: "ABBCCCDCEFDDDDDDEEEEEEEEFFFFFFFFF"

  34. 34

    Returns: "ABBCCCCDEFDDDDDDDEEEEEEEEFFFFFFFFF"

  35. 35

    Returns: "ABBCCCCDEDFDDDDDDEEEEEEEEFFFFFFFFFF"

  36. 36

    Returns: "ABBCCCCDDEFDDDDDDEEEEEEEEEFFFFFFFFFF"

  37. 37

    Returns: "ABBCCCCDDEDFDDDDDEEEEEEEEEFFFFFFFFFFF"

  38. 38

    Returns: "ABBCCCCDDDEFDDDDDEEEEEEEEEEFFFFFFFFFFF"

  39. 39

    Returns: "ABBCCCCDDDEDFDDDDEEEEEEEEEEFFFFFFFFFFFF"

  40. 40

    Returns: "ABBCCCCDDDDEFDDDDEEEEEEEEEEEFFFFFFFFFFFF"

  41. 41

    Returns: "ABBCCCCDDDDEDFDDDEEEEEEEEEEEFFFFFFFFFFFFF"

  42. 42

    Returns: "ABBCCCCDDDDDEFDDDEEEEEEEEEEEEFFFFFFFFFFFFF"

  43. 43

    Returns: "ABBCCCCDDDDDEDFDDEEEEEEEEEEEEFFFFFFFFFFFFFF"

  44. 44

    Returns: "ABBCCCCDDDDDDEFDDEEEEEEEEEEEEEFFFFFFFFFFFFFF"

  45. 45

    Returns: "ABBCCCCDDDDDDEDFDEEEEEEEEEEEEEFFFFFFFFFFFFFFF"

  46. 46

    Returns: "ABBCCCCDDDDDDDEFDEEEEEEEEEEEEEEFFFFFFFFFFFFFFF"

  47. 47

    Returns: "ABBCCCCDDDDDDDEDFEEEEEEEEEEEEEEFFFFFFFFFFFFFFFF"

  48. 48

    Returns: "ABBCCCCDDDDDDDDEFEEEEEEEEEEEEEEEFFFFFFFFFFFFFFFF"

  49. 49

    Returns: "ABBCCCCDDDDDDDDEEFEEEEEEEEEEEEEEFFFFFFFFFFFFFFFFF"

  50. 50

    Returns: "ABBCCCCDDDDDDDDEEEFEEEEEEEEEEEEEFFFFFFFFFFFFFFFFFF"

  51. 51

    Returns: "ABBCCCCDDDDDDDDEEEEFEEEEEEEEEEEEFFFFFFFFFFFFFFFFFFF"

  52. 52

    Returns: "ABBCCCCDDDDDDDDEEEEEFEEEEEEEEEEEFFFFFFFFFFFFFFFFFFFF"

  53. 53

    Returns: "ABBCCCCDDDDDDDDEEEEEEFEEEEEEEEEEFFFFFFFFFFFFFFFFFFFFF"

  54. 54

    Returns: "ABBCCCCDDDDDDDDEEEEEEEFEEEEEEEEEFFFFFFFFFFFFFFFFFFFFFF"

  55. 55

    Returns: "ABBCCCCDDDDDDDDEEEEEEEEFEEEEEEEEFFFFFFFFFFFFFFFFFFFFFFF"

  56. 56

    Returns: "ABBCCCCDDDDDDDDEEEEEEEEEFEEEEEEEFFFFFFFFFFFFFFFFFFFFFFFF"

  57. 57

    Returns: "ABBCCCCDDDDDDDDEEEEEEEEEEFEEEEEEFFFFFFFFFFFFFFFFFFFFFFFFF"

  58. 58

    Returns: "ABBCCCCDDDDDDDDEEEEEEEEEEEFEEEEEFFFFFFFFFFFFFFFFFFFFFFFFFF"

  59. 59

    Returns: "ABBCCCCDDDDDDDDEEEEEEEEEEEEFEEEEFFFFFFFFFFFFFFFFFFFFFFFFFFF"

  60. 60

    Returns: "ABBCCCCDDDDDDDDEEEEEEEEEEEEEFEEEFFFFFFFFFFFFFFFFFFFFFFFFFFFF"

  61. 61

    Returns: "ABBCCCCDDDDDDDDEEEEEEEEEEEEEEFEEFFFFFFFFFFFFFFFFFFFFFFFFFFFFF"

  62. 62

    Returns: "ABBCCCCDDDDDDDDEEEEEEEEEEEEEEEFEFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF"

  63. 63

    Returns: "ABBCCCCDDDDDDDDEEEEEEEEEEEEEEEEFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF"

  64. 64

    Returns: "ABBCCCCDDDDDDDEFDGEEEEEEEEEEEEEEFFFFFFFFFFFFFFFGGGGGGGGGGGGGGGGG"

  65. 65

    Returns: "ABBCCCCDDDDDDDEDFGEEEEEEEEEEEEEEFFFFFFFFFFFFFFFFGGGGGGGGGGGGGGGGG"

  66. 66

    Returns: "ABBCCCCDDDDDDDDEFGEEEEEEEEEEEEEEEFFFFFFFFFFFFFFFFGGGGGGGGGGGGGGGGG"

  67. 67

    Returns: "ABBCCCCDDDDDDDDEFEGEEEEEEEEEEEEEEFFFFFFFFFFFFFFFFGGGGGGGGGGGGGGGGGG"

  68. 68

    Returns: "ABBCCCCDDDDDDDDEEFGEEEEEEEEEEEEEEFFFFFFFFFFFFFFFFFGGGGGGGGGGGGGGGGGG"

  69. 69

    Returns: "ABBCCCCDDDDDDDDEEFEGEEEEEEEEEEEEEFFFFFFFFFFFFFFFFFGGGGGGGGGGGGGGGGGGG"

  70. 70

    Returns: "ABBCCCCDDDDDDDDEEEFGEEEEEEEEEEEEEFFFFFFFFFFFFFFFFFFGGGGGGGGGGGGGGGGGGG"

  71. 71

    Returns: "ABBCCCCDDDDDDDDEEEFEGEEEEEEEEEEEEFFFFFFFFFFFFFFFFFFGGGGGGGGGGGGGGGGGGGG"

  72. 72

    Returns: "ABBCCCCDDDDDDDDEEEEFGEEEEEEEEEEEEFFFFFFFFFFFFFFFFFFFGGGGGGGGGGGGGGGGGGGG"

  73. 73

    Returns: "ABBCCCCDDDDDDDDEEEEFEGEEEEEEEEEEEFFFFFFFFFFFFFFFFFFFGGGGGGGGGGGGGGGGGGGGG"

  74. 74

    Returns: "ABBCCCCDDDDDDDDEEEEEFGEEEEEEEEEEEFFFFFFFFFFFFFFFFFFFFGGGGGGGGGGGGGGGGGGGGG"

  75. 75

    Returns: "ABBCCCCDDDDDDDDEEEEEFEGEEEEEEEEEEFFFFFFFFFFFFFFFFFFFFGGGGGGGGGGGGGGGGGGGGGG"

  76. 76

    Returns: "ABBCCCCDDDDDDDDEEEEEEFGEEEEEEEEEEFFFFFFFFFFFFFFFFFFFFFGGGGGGGGGGGGGGGGGGGGGG"

  77. 77

    Returns: "ABBCCCCDDDDDDDDEEEEEEFEGEEEEEEEEEFFFFFFFFFFFFFFFFFFFFFGGGGGGGGGGGGGGGGGGGGGGG"

  78. 78

    Returns: "ABBCCCCDDDDDDDDEEEEEEEFGEEEEEEEEEFFFFFFFFFFFFFFFFFFFFFFGGGGGGGGGGGGGGGGGGGGGGG"

  79. 79

    Returns: "ABBCCCCDDDDDDDDEEEEEEEFEGEEEEEEEEFFFFFFFFFFFFFFFFFFFFFFGGGGGGGGGGGGGGGGGGGGGGGG"

  80. 80

    Returns: "ABBCCCCDDDDDDDDEEEEEEEEFGEEEEEEEEFFFFFFFFFFFFFFFFFFFFFFFGGGGGGGGGGGGGGGGGGGGGGGG"

  81. 81

    Returns: "ABBCCCCDDDDDDDDEEEEEEEEFEGEEEEEEEFFFFFFFFFFFFFFFFFFFFFFFGGGGGGGGGGGGGGGGGGGGGGGGG"

  82. 82

    Returns: "ABBCCCCDDDDDDDDEEEEEEEEEFGEEEEEEEFFFFFFFFFFFFFFFFFFFFFFFFGGGGGGGGGGGGGGGGGGGGGGGGG"

  83. 83

    Returns: "ABBCCCCDDDDDDDDEEEEEEEEEFEGEEEEEEFFFFFFFFFFFFFFFFFFFFFFFFGGGGGGGGGGGGGGGGGGGGGGGGGG"

  84. 84

    Returns: "ABBCCCCDDDDDDDDEEEEEEEEEEFGEEEEEEFFFFFFFFFFFFFFFFFFFFFFFFFGGGGGGGGGGGGGGGGGGGGGGGGGG"

  85. 85

    Returns: "ABBCCCCDDDDDDDDEEEEEEEEEEFEGEEEEEFFFFFFFFFFFFFFFFFFFFFFFFFGGGGGGGGGGGGGGGGGGGGGGGGGGG"

  86. 86

    Returns: "ABBCCCCDDDDDDDDEEEEEEEEEEEFGEEEEEFFFFFFFFFFFFFFFFFFFFFFFFFFGGGGGGGGGGGGGGGGGGGGGGGGGGG"

  87. 87

    Returns: "ABBCCCCDDDDDDDDEEEEEEEEEEEFEGEEEEFFFFFFFFFFFFFFFFFFFFFFFFFFGGGGGGGGGGGGGGGGGGGGGGGGGGGG"

  88. 88

    Returns: "ABBCCCCDDDDDDDDEEEEEEEEEEEEFGEEEEFFFFFFFFFFFFFFFFFFFFFFFFFFFGGGGGGGGGGGGGGGGGGGGGGGGGGGG"

  89. 89

    Returns: "ABBCCCCDDDDDDDDEEEEEEEEEEEEFEGEEEFFFFFFFFFFFFFFFFFFFFFFFFFFFGGGGGGGGGGGGGGGGGGGGGGGGGGGGG"

  90. 90

    Returns: "ABBCCCCDDDDDDDDEEEEEEEEEEEEEFGEEEFFFFFFFFFFFFFFFFFFFFFFFFFFFFGGGGGGGGGGGGGGGGGGGGGGGGGGGGG"

  91. 91

    Returns: "ABBCCCCDDDDDDDDEEEEEEEEEEEEEFEGEEFFFFFFFFFFFFFFFFFFFFFFFFFFFFGGGGGGGGGGGGGGGGGGGGGGGGGGGGGG"

  92. 92

    Returns: "ABBCCCCDDDDDDDDEEEEEEEEEEEEEEFGEEFFFFFFFFFFFFFFFFFFFFFFFFFFFFFGGGGGGGGGGGGGGGGGGGGGGGGGGGGGG"

  93. 93

    Returns: "ABBCCCCDDDDDDDDEEEEEEEEEEEEEEFEGEFFFFFFFFFFFFFFFFFFFFFFFFFFFFFGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGG"

  94. 94

    Returns: "ABBCCCCDDDDDDDDEEEEEEEEEEEEEEEFGEFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGG"

  95. 95

    Returns: "ABBCCCCDDDDDDDDEEEEEEEEEEEEEEEFEGFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGG"

  96. 96

    Returns: "ABBCCCCDDDDDDDDEEEEEEEEEEEEEEEEFGFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGG"

  97. 97

    Returns: "ABBCCCCDDDDDDDDEEEEEEEEEEEEEEEEFFGFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGG"

  98. 98

    Returns: "ABBCCCCDDDDDDDDEEEEEEEEEEEEEEEEFFFGFFFFFFFFFFFFFFFFFFFFFFFFFFFFFGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGG"

  99. 99

    Returns: "ABBCCCCDDDDDDDDEEEEEEEEEEEEEEEEFFFFGFFFFFFFFFFFFFFFFFFFFFFFFFFFFGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGG"

  100. 100

    Returns: "ABBCCCCDDDDDDDDEEEEEEEEEEEEEEEEFFFFFGFFFFFFFFFFFFFFFFFFFFFFFFFFFGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGG"

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: