Statistics

Problem Statement for "DerivationDisplay"

Problem Statement

  S ::= T | bUa
  T ::= aTb | A | B
  U ::= aU | bU | a | b
  A ::= aA | a
  B ::= bB | b
Displayed above is a Context-Free Grammar (CFG). You begin with the string (quotes for clarity) "S", and apply replacement rules until your resulting string no longer contains any capital letters. The first line above says that S can be replaced with T or bUa. The other lines are similar. You will return a sequence of strings, beginning with "S" and ending with input, where each successive sequence element results from applying one of the replacement rules above. For example, if input is "aaabb" then you will return 
 {"S","T","aTb","aaTbb","aaAbb","aaabb"}

Definition

Class:
DerivationDisplay
Method:
getDerivation
Parameters:
String
Returns:
String[]
Method signature:
String[] getDerivation(String input)
(be sure your method is public)

Constraints

  • input will contain between 1 and 50 characters inclusive.
  • Each character in input will be 'a' or 'b'.
  • There will be exactly one solution.

Examples

  1. "baabba"

    Returns: {"S", "bUa", "baUa", "baaUa", "baabUa", "baabba" }

  2. "aaabb"

    Returns: {"S", "T", "aTb", "aaTbb", "aaAbb", "aaabb" }

    The example above.

  3. "bbba"

    Returns: {"S", "bUa", "bbUa", "bbba" }

    In the first step, S must be replaced with bUa in order to derive this string. Then the 2 inner b's are added.

  4. "baabba"

    Returns: {"S", "bUa", "baUa", "baaUa", "baabUa", "baabba" }

  5. "a"

    Returns: {"S", "T", "A", "a" }

  6. "b"

    Returns: {"S", "T", "B", "b" }

  7. "aabbbbbbbb"

    Returns: {"S", "T", "aTb", "aaTbb", "aaBbb", "aabBbb", "aabbBbb", "aabbbBbb", "aabbbbBbb", "aabbbbbBbb", "aabbbbbbbb" }

  8. "aaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbb"

    Returns: {"S", "T", "aTb", "aaTbb", "aaaTbbb", "aaaaTbbbb", "aaaaaTbbbbb", "aaaaaaTbbbbbb", "aaaaaaaTbbbbbbb", "aaaaaaaaTbbbbbbbb", "aaaaaaaaaTbbbbbbbbb", "aaaaaaaaaaTbbbbbbbbbb", "aaaaaaaaaaaTbbbbbbbbbbb", "aaaaaaaaaaaaTbbbbbbbbbbbb", "aaaaaaaaaaaaaTbbbbbbbbbbbbb", "aaaaaaaaaaaaaaTbbbbbbbbbbbbbb", "aaaaaaaaaaaaaaaTbbbbbbbbbbbbbbb", "aaaaaaaaaaaaaaaaTbbbbbbbbbbbbbbbb", "aaaaaaaaaaaaaaaaaTbbbbbbbbbbbbbbbbb", "aaaaaaaaaaaaaaaaaaTbbbbbbbbbbbbbbbbbb", "aaaaaaaaaaaaaaaaaaaTbbbbbbbbbbbbbbbbbbb", "aaaaaaaaaaaaaaaaaaaaTbbbbbbbbbbbbbbbbbbbb", "aaaaaaaaaaaaaaaaaaaaBbbbbbbbbbbbbbbbbbbbb", "aaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbb" }

  9. "aaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbb"

    Returns: {"S", "T", "aTb", "aaTbb", "aaaTbbb", "aaaaTbbbb", "aaaaaTbbbbb", "aaaaaaTbbbbbb", "aaaaaaaTbbbbbbb", "aaaaaaaaTbbbbbbbb", "aaaaaaaaaTbbbbbbbbb", "aaaaaaaaaaTbbbbbbbbbb", "aaaaaaaaaaaTbbbbbbbbbbb", "aaaaaaaaaaaaTbbbbbbbbbbbb", "aaaaaaaaaaaaaTbbbbbbbbbbbbb", "aaaaaaaaaaaaaaTbbbbbbbbbbbbbb", "aaaaaaaaaaaaaaaTbbbbbbbbbbbbbbb", "aaaaaaaaaaaaaaaaTbbbbbbbbbbbbbbbb", "aaaaaaaaaaaaaaaaaTbbbbbbbbbbbbbbbbb", "aaaaaaaaaaaaaaaaaaTbbbbbbbbbbbbbbbbbb", "aaaaaaaaaaaaaaaaaaaTbbbbbbbbbbbbbbbbbbb", "aaaaaaaaaaaaaaaaaaaaTbbbbbbbbbbbbbbbbbbbb", "aaaaaaaaaaaaaaaaaaaaAbbbbbbbbbbbbbbbbbbbb", "aaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbb" }

  10. "abbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb"

    Returns: {"S", "T", "aTb", "aBb", "abBb", "abbBb", "abbbBb", "abbbbBb", "abbbbbBb", "abbbbbbBb", "abbbbbbbBb", "abbbbbbbbBb", "abbbbbbbbbBb", "abbbbbbbbbbBb", "abbbbbbbbbbbBb", "abbbbbbbbbbbbBb", "abbbbbbbbbbbbbBb", "abbbbbbbbbbbbbbBb", "abbbbbbbbbbbbbbbBb", "abbbbbbbbbbbbbbbbBb", "abbbbbbbbbbbbbbbbbBb", "abbbbbbbbbbbbbbbbbbBb", "abbbbbbbbbbbbbbbbbbbBb", "abbbbbbbbbbbbbbbbbbbbBb", "abbbbbbbbbbbbbbbbbbbbbBb", "abbbbbbbbbbbbbbbbbbbbbbBb", "abbbbbbbbbbbbbbbbbbbbbbbBb", "abbbbbbbbbbbbbbbbbbbbbbbbBb", "abbbbbbbbbbbbbbbbbbbbbbbbbBb", "abbbbbbbbbbbbbbbbbbbbbbbbbbBb", "abbbbbbbbbbbbbbbbbbbbbbbbbbbBb", "abbbbbbbbbbbbbbbbbbbbbbbbbbbbBb", "abbbbbbbbbbbbbbbbbbbbbbbbbbbbbBb", "abbbbbbbbbbbbbbbbbbbbbbbbbbbbbbBb", "abbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbBb", "abbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbBb", "abbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbBb", "abbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbBb", "abbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbBb", "abbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbBb", "abbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbBb", "abbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbBb", "abbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb" }

  11. "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab"

    Returns: {"S", "T", "aTb", "aAb", "aaAb", "aaaAb", "aaaaAb", "aaaaaAb", "aaaaaaAb", "aaaaaaaAb", "aaaaaaaaAb", "aaaaaaaaaAb", "aaaaaaaaaaAb", "aaaaaaaaaaaAb", "aaaaaaaaaaaaAb", "aaaaaaaaaaaaaAb", "aaaaaaaaaaaaaaAb", "aaaaaaaaaaaaaaaAb", "aaaaaaaaaaaaaaaaAb", "aaaaaaaaaaaaaaaaaAb", "aaaaaaaaaaaaaaaaaaAb", "aaaaaaaaaaaaaaaaaaaAb", "aaaaaaaaaaaaaaaaaaaaAb", "aaaaaaaaaaaaaaaaaaaaaAb", "aaaaaaaaaaaaaaaaaaaaaaAb", "aaaaaaaaaaaaaaaaaaaaaaaAb", "aaaaaaaaaaaaaaaaaaaaaaaaAb", "aaaaaaaaaaaaaaaaaaaaaaaaaAb", "aaaaaaaaaaaaaaaaaaaaaaaaaaAb", "aaaaaaaaaaaaaaaaaaaaaaaaaaaAb", "aaaaaaaaaaaaaaaaaaaaaaaaaaaaAb", "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaAb", "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaAb", "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaAb", "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaAb", "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaAb", "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaAb", "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaAb", "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaAb", "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaAb", "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaAb", "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaAb", "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaAb", "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaAb", "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaAb", "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaAb", "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab" }

  12. "aaaaaaaaaaaaaaaaaaaaaaaaaaaa"

    Returns: {"S", "T", "A", "aA", "aaA", "aaaA", "aaaaA", "aaaaaA", "aaaaaaA", "aaaaaaaA", "aaaaaaaaA", "aaaaaaaaaA", "aaaaaaaaaaA", "aaaaaaaaaaaA", "aaaaaaaaaaaaA", "aaaaaaaaaaaaaA", "aaaaaaaaaaaaaaA", "aaaaaaaaaaaaaaaA", "aaaaaaaaaaaaaaaaA", "aaaaaaaaaaaaaaaaaA", "aaaaaaaaaaaaaaaaaaA", "aaaaaaaaaaaaaaaaaaaA", "aaaaaaaaaaaaaaaaaaaaA", "aaaaaaaaaaaaaaaaaaaaaA", "aaaaaaaaaaaaaaaaaaaaaaA", "aaaaaaaaaaaaaaaaaaaaaaaA", "aaaaaaaaaaaaaaaaaaaaaaaaA", "aaaaaaaaaaaaaaaaaaaaaaaaaA", "aaaaaaaaaaaaaaaaaaaaaaaaaaA", "aaaaaaaaaaaaaaaaaaaaaaaaaaaA", "aaaaaaaaaaaaaaaaaaaaaaaaaaaa" }

  13. "bbbbbbbbbbbbbbbbbbbbbbbbbbbb"

    Returns: {"S", "T", "B", "bB", "bbB", "bbbB", "bbbbB", "bbbbbB", "bbbbbbB", "bbbbbbbB", "bbbbbbbbB", "bbbbbbbbbB", "bbbbbbbbbbB", "bbbbbbbbbbbB", "bbbbbbbbbbbbB", "bbbbbbbbbbbbbB", "bbbbbbbbbbbbbbB", "bbbbbbbbbbbbbbbB", "bbbbbbbbbbbbbbbbB", "bbbbbbbbbbbbbbbbbB", "bbbbbbbbbbbbbbbbbbB", "bbbbbbbbbbbbbbbbbbbB", "bbbbbbbbbbbbbbbbbbbbB", "bbbbbbbbbbbbbbbbbbbbbB", "bbbbbbbbbbbbbbbbbbbbbbB", "bbbbbbbbbbbbbbbbbbbbbbbB", "bbbbbbbbbbbbbbbbbbbbbbbbB", "bbbbbbbbbbbbbbbbbbbbbbbbbB", "bbbbbbbbbbbbbbbbbbbbbbbbbbB", "bbbbbbbbbbbbbbbbbbbbbbbbbbbB", "bbbbbbbbbbbbbbbbbbbbbbbbbbbb" }

  14. "babababababababaabababababa"

    Returns: {"S", "bUa", "baUa", "babUa", "babaUa", "bababUa", "bababaUa", "babababUa", "babababaUa", "bababababUa", "bababababaUa", "babababababUa", "babababababaUa", "bababababababUa", "bababababababaUa", "babababababababUa", "babababababababaUa", "babababababababaaUa", "babababababababaabUa", "babababababababaabaUa", "babababababababaababUa", "babababababababaababaUa", "babababababababaabababUa", "babababababababaabababaUa", "babababababababaababababUa", "babababababababaababababaUa", "babababababababaabababababa" }

  15. "baaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"

    Returns: {"S", "bUa", "baUa", "baaUa", "baaaUa", "baaaaUa", "baaaaaUa", "baaaaaaUa", "baaaaaaaUa", "baaaaaaaaUa", "baaaaaaaaaUa", "baaaaaaaaaaUa", "baaaaaaaaaaaUa", "baaaaaaaaaaaaUa", "baaaaaaaaaaaaaUa", "baaaaaaaaaaaaaaUa", "baaaaaaaaaaaaaaaUa", "baaaaaaaaaaaaaaaaUa", "baaaaaaaaaaaaaaaaaUa", "baaaaaaaaaaaaaaaaaaUa", "baaaaaaaaaaaaaaaaaaaUa", "baaaaaaaaaaaaaaaaaaaaUa", "baaaaaaaaaaaaaaaaaaaaaUa", "baaaaaaaaaaaaaaaaaaaaaaUa", "baaaaaaaaaaaaaaaaaaaaaaaUa", "baaaaaaaaaaaaaaaaaaaaaaaaUa", "baaaaaaaaaaaaaaaaaaaaaaaaaUa", "baaaaaaaaaaaaaaaaaaaaaaaaaaUa", "baaaaaaaaaaaaaaaaaaaaaaaaaaaUa", "baaaaaaaaaaaaaaaaaaaaaaaaaaaaUa", "baaaaaaaaaaaaaaaaaaaaaaaaaaaaaUa", "baaaaaaaaaaaaaaaaaaaaaaaaaaaaaaUa", "baaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaUa", "baaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaUa", "baaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaUa", "baaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaUa", "baaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaUa", "baaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaUa", "baaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaUa", "baaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaUa", "baaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa" }

  16. "baaaaaaaaaabbbbbbbbbbbbbbbbbbba"

    Returns: {"S", "bUa", "baUa", "baaUa", "baaaUa", "baaaaUa", "baaaaaUa", "baaaaaaUa", "baaaaaaaUa", "baaaaaaaaUa", "baaaaaaaaaUa", "baaaaaaaaaaUa", "baaaaaaaaaabUa", "baaaaaaaaaabbUa", "baaaaaaaaaabbbUa", "baaaaaaaaaabbbbUa", "baaaaaaaaaabbbbbUa", "baaaaaaaaaabbbbbbUa", "baaaaaaaaaabbbbbbbUa", "baaaaaaaaaabbbbbbbbUa", "baaaaaaaaaabbbbbbbbbUa", "baaaaaaaaaabbbbbbbbbbUa", "baaaaaaaaaabbbbbbbbbbbUa", "baaaaaaaaaabbbbbbbbbbbbUa", "baaaaaaaaaabbbbbbbbbbbbbUa", "baaaaaaaaaabbbbbbbbbbbbbbUa", "baaaaaaaaaabbbbbbbbbbbbbbbUa", "baaaaaaaaaabbbbbbbbbbbbbbbbUa", "baaaaaaaaaabbbbbbbbbbbbbbbbbUa", "baaaaaaaaaabbbbbbbbbbbbbbbbbbUa", "baaaaaaaaaabbbbbbbbbbbbbbbbbbba" }

  17. "bababababababbabbaaababaabaaaababababababa"

    Returns: {"S", "bUa", "baUa", "babUa", "babaUa", "bababUa", "bababaUa", "babababUa", "babababaUa", "bababababUa", "bababababaUa", "babababababUa", "babababababaUa", "bababababababUa", "bababababababbUa", "bababababababbaUa", "bababababababbabUa", "bababababababbabbUa", "bababababababbabbaUa", "bababababababbabbaaUa", "bababababababbabbaaaUa", "bababababababbabbaaabUa", "bababababababbabbaaabaUa", "bababababababbabbaaababUa", "bababababababbabbaaababaUa", "bababababababbabbaaababaaUa", "bababababababbabbaaababaabUa", "bababababababbabbaaababaabaUa", "bababababababbabbaaababaabaaUa", "bababababababbabbaaababaabaaaUa", "bababababababbabbaaababaabaaaaUa", "bababababababbabbaaababaabaaaabUa", "bababababababbabbaaababaabaaaabaUa", "bababababababbabbaaababaabaaaababUa", "bababababababbabbaaababaabaaaababaUa", "bababababababbabbaaababaabaaaabababUa", "bababababababbabbaaababaabaaaabababaUa", "bababababababbabbaaababaabaaaababababUa", "bababababababbabbaaababaabaaaababababaUa", "bababababababbabbaaababaabaaaabababababUa", "bababababababbabbaaababaabaaaabababababaUa", "bababababababbabbaaababaabaaaababababababa" }

  18. "aaaaaaaaaaabbbbbbbbbbbbbbbbbbb"

    Returns: {"S", "T", "aTb", "aaTbb", "aaaTbbb", "aaaaTbbbb", "aaaaaTbbbbb", "aaaaaaTbbbbbb", "aaaaaaaTbbbbbbb", "aaaaaaaaTbbbbbbbb", "aaaaaaaaaTbbbbbbbbb", "aaaaaaaaaaTbbbbbbbbbb", "aaaaaaaaaaaTbbbbbbbbbbb", "aaaaaaaaaaaBbbbbbbbbbbb", "aaaaaaaaaaabBbbbbbbbbbbb", "aaaaaaaaaaabbBbbbbbbbbbbb", "aaaaaaaaaaabbbBbbbbbbbbbbb", "aaaaaaaaaaabbbbBbbbbbbbbbbb", "aaaaaaaaaaabbbbbBbbbbbbbbbbb", "aaaaaaaaaaabbbbbbBbbbbbbbbbbb", "aaaaaaaaaaabbbbbbbBbbbbbbbbbbb", "aaaaaaaaaaabbbbbbbbbbbbbbbbbbb" }

  19. "baa"

    Returns: {"S", "bUa", "baa" }

  20. "bba"

    Returns: {"S", "bUa", "bba" }

  21. "aab"

    Returns: {"S", "T", "aTb", "aAb", "aab" }

  22. "abb"

    Returns: {"S", "T", "aTb", "aBb", "abb" }

  23. "aabbbbbbbb"

    Returns: {"S", "T", "aTb", "aaTbb", "aaBbb", "aabBbb", "aabbBbb", "aabbbBbb", "aabbbbBbb", "aabbbbbBbb", "aabbbbbbbb" }

  24. "aaaa"

    Returns: {"S", "T", "A", "aA", "aaA", "aaaA", "aaaa" }

  25. "baabba"

    Returns: {"S", "bUa", "baUa", "baaUa", "baabUa", "baabba" }

  26. "aab"

    Returns: {"S", "T", "aTb", "aAb", "aab" }

  27. "b"

    Returns: {"S", "T", "B", "b" }

  28. "bb"

    Returns: {"S", "T", "B", "bB", "bb" }

  29. "aaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbb"

    Returns: {"S", "T", "aTb", "aaTbb", "aaaTbbb", "aaaaTbbbb", "aaaaaTbbbbb", "aaaaaaTbbbbbb", "aaaaaaaTbbbbbbb", "aaaaaaaaTbbbbbbbb", "aaaaaaaaaTbbbbbbbbb", "aaaaaaaaaBbbbbbbbbb", "aaaaaaaaabBbbbbbbbbb", "aaaaaaaaabbBbbbbbbbbb", "aaaaaaaaabbbBbbbbbbbbb", "aaaaaaaaabbbbBbbbbbbbbb", "aaaaaaaaabbbbbBbbbbbbbbb", "aaaaaaaaabbbbbbBbbbbbbbbb", "aaaaaaaaabbbbbbbBbbbbbbbbb", "aaaaaaaaabbbbbbbbBbbbbbbbbb", "aaaaaaaaabbbbbbbbbBbbbbbbbbb", "aaaaaaaaabbbbbbbbbbBbbbbbbbbb", "aaaaaaaaabbbbbbbbbbbBbbbbbbbbb", "aaaaaaaaabbbbbbbbbbbbBbbbbbbbbb", "aaaaaaaaabbbbbbbbbbbbbBbbbbbbbbb", "aaaaaaaaabbbbbbbbbbbbbbBbbbbbbbbb", "aaaaaaaaabbbbbbbbbbbbbbbBbbbbbbbbb", "aaaaaaaaabbbbbbbbbbbbbbbbBbbbbbbbbb", "aaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbb" }

  30. "baa"

    Returns: {"S", "bUa", "baa" }

  31. "babbbbbbbbaaaaabbbbbbaaababbbbbbbbbaaaaabbbbbababa"

    Returns: {"S", "bUa", "baUa", "babUa", "babbUa", "babbbUa", "babbbbUa", "babbbbbUa", "babbbbbbUa", "babbbbbbbUa", "babbbbbbbbUa", "babbbbbbbbaUa", "babbbbbbbbaaUa", "babbbbbbbbaaaUa", "babbbbbbbbaaaaUa", "babbbbbbbbaaaaaUa", "babbbbbbbbaaaaabUa", "babbbbbbbbaaaaabbUa", "babbbbbbbbaaaaabbbUa", "babbbbbbbbaaaaabbbbUa", "babbbbbbbbaaaaabbbbbUa", "babbbbbbbbaaaaabbbbbbUa", "babbbbbbbbaaaaabbbbbbaUa", "babbbbbbbbaaaaabbbbbbaaUa", "babbbbbbbbaaaaabbbbbbaaaUa", "babbbbbbbbaaaaabbbbbbaaabUa", "babbbbbbbbaaaaabbbbbbaaabaUa", "babbbbbbbbaaaaabbbbbbaaababUa", "babbbbbbbbaaaaabbbbbbaaababbUa", "babbbbbbbbaaaaabbbbbbaaababbbUa", "babbbbbbbbaaaaabbbbbbaaababbbbUa", "babbbbbbbbaaaaabbbbbbaaababbbbbUa", "babbbbbbbbaaaaabbbbbbaaababbbbbbUa", "babbbbbbbbaaaaabbbbbbaaababbbbbbbUa", "babbbbbbbbaaaaabbbbbbaaababbbbbbbbUa", "babbbbbbbbaaaaabbbbbbaaababbbbbbbbbUa", "babbbbbbbbaaaaabbbbbbaaababbbbbbbbbaUa", "babbbbbbbbaaaaabbbbbbaaababbbbbbbbbaaUa", "babbbbbbbbaaaaabbbbbbaaababbbbbbbbbaaaUa", "babbbbbbbbaaaaabbbbbbaaababbbbbbbbbaaaaUa", "babbbbbbbbaaaaabbbbbbaaababbbbbbbbbaaaaaUa", "babbbbbbbbaaaaabbbbbbaaababbbbbbbbbaaaaabUa", "babbbbbbbbaaaaabbbbbbaaababbbbbbbbbaaaaabbUa", "babbbbbbbbaaaaabbbbbbaaababbbbbbbbbaaaaabbbUa", "babbbbbbbbaaaaabbbbbbaaababbbbbbbbbaaaaabbbbUa", "babbbbbbbbaaaaabbbbbbaaababbbbbbbbbaaaaabbbbbUa", "babbbbbbbbaaaaabbbbbbaaababbbbbbbbbaaaaabbbbbaUa", "babbbbbbbbaaaaabbbbbbaaababbbbbbbbbaaaaabbbbbabUa", "babbbbbbbbaaaaabbbbbbaaababbbbbbbbbaaaaabbbbbabaUa", "babbbbbbbbaaaaabbbbbbaaababbbbbbbbbaaaaabbbbbababa" }

  32. "aaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbb"

    Returns: {"S", "T", "aTb", "aaTbb", "aaaTbbb", "aaaaTbbbb", "aaaaaTbbbbb", "aaaaaaTbbbbbb", "aaaaaaaTbbbbbbb", "aaaaaaaaTbbbbbbbb", "aaaaaaaaaTbbbbbbbbb", "aaaaaaaaaaTbbbbbbbbbb", "aaaaaaaaaaaTbbbbbbbbbbb", "aaaaaaaaaaaaTbbbbbbbbbbbb", "aaaaaaaaaaaaaTbbbbbbbbbbbbb", "aaaaaaaaaaaaaaTbbbbbbbbbbbbbb", "aaaaaaaaaaaaaaaTbbbbbbbbbbbbbbb", "aaaaaaaaaaaaaaaaTbbbbbbbbbbbbbbbb", "aaaaaaaaaaaaaaaaaTbbbbbbbbbbbbbbbbb", "aaaaaaaaaaaaaaaaaaTbbbbbbbbbbbbbbbbbb", "aaaaaaaaaaaaaaaaaaaTbbbbbbbbbbbbbbbbbbb", "aaaaaaaaaaaaaaaaaaaaTbbbbbbbbbbbbbbbbbbbb", "aaaaaaaaaaaaaaaaaaaaaTbbbbbbbbbbbbbbbbbbbbb", "aaaaaaaaaaaaaaaaaaaaaaTbbbbbbbbbbbbbbbbbbbbbb", "aaaaaaaaaaaaaaaaaaaaaaaTbbbbbbbbbbbbbbbbbbbbbbb", "aaaaaaaaaaaaaaaaaaaaaaaaTbbbbbbbbbbbbbbbbbbbbbbbb", "aaaaaaaaaaaaaaaaaaaaaaaaAbbbbbbbbbbbbbbbbbbbbbbbb", "aaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbb" }

  33. "babababababababababababababababababababababababaa"

    Returns: {"S", "bUa", "baUa", "babUa", "babaUa", "bababUa", "bababaUa", "babababUa", "babababaUa", "bababababUa", "bababababaUa", "babababababUa", "babababababaUa", "bababababababUa", "bababababababaUa", "babababababababUa", "babababababababaUa", "bababababababababUa", "bababababababababaUa", "babababababababababUa", "babababababababababaUa", "bababababababababababUa", "bababababababababababaUa", "babababababababababababUa", "babababababababababababaUa", "bababababababababababababUa", "bababababababababababababaUa", "babababababababababababababUa", "babababababababababababababaUa", "bababababababababababababababUa", "bababababababababababababababaUa", "babababababababababababababababUa", "babababababababababababababababaUa", "bababababababababababababababababUa", "bababababababababababababababababaUa", "babababababababababababababababababUa", "babababababababababababababababababaUa", "bababababababababababababababababababUa", "bababababababababababababababababababaUa", "babababababababababababababababababababUa", "babababababababababababababababababababaUa", "bababababababababababababababababababababUa", "bababababababababababababababababababababaUa", "babababababababababababababababababababababUa", "babababababababababababababababababababababaUa", "bababababababababababababababababababababababUa", "bababababababababababababababababababababababaUa", "babababababababababababababababababababababababUa", "babababababababababababababababababababababababaa" }

  34. "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"

    Returns: {"S", "T", "A", "aA", "aaA", "aaaA", "aaaaA", "aaaaaA", "aaaaaaA", "aaaaaaaA", "aaaaaaaaA", "aaaaaaaaaA", "aaaaaaaaaaA", "aaaaaaaaaaaA", "aaaaaaaaaaaaA", "aaaaaaaaaaaaaA", "aaaaaaaaaaaaaaA", "aaaaaaaaaaaaaaaA", "aaaaaaaaaaaaaaaaA", "aaaaaaaaaaaaaaaaaA", "aaaaaaaaaaaaaaaaaaA", "aaaaaaaaaaaaaaaaaaaA", "aaaaaaaaaaaaaaaaaaaaA", "aaaaaaaaaaaaaaaaaaaaaA", "aaaaaaaaaaaaaaaaaaaaaaA", "aaaaaaaaaaaaaaaaaaaaaaaA", "aaaaaaaaaaaaaaaaaaaaaaaaA", "aaaaaaaaaaaaaaaaaaaaaaaaaA", "aaaaaaaaaaaaaaaaaaaaaaaaaaA", "aaaaaaaaaaaaaaaaaaaaaaaaaaaA", "aaaaaaaaaaaaaaaaaaaaaaaaaaaaA", "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaA", "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaA", "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaA", "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaA", "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaA", "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaA", "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaA", "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaA", "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaA", "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaA", "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaA", "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaA", "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaA", "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaA", "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaA", "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaA", "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaA", "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaA", "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaA", "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaA", "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaA", "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa" }

  35. "bbbbbbbbbb"

    Returns: {"S", "T", "B", "bB", "bbB", "bbbB", "bbbbB", "bbbbbB", "bbbbbbB", "bbbbbbbB", "bbbbbbbbB", "bbbbbbbbbB", "bbbbbbbbbb" }

  36. "bbbaaba"

    Returns: {"S", "bUa", "bbUa", "bbbUa", "bbbaUa", "bbbaaUa", "bbbaaba" }

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: