Statistics

Problem Statement for "Stringhalving"

Problem Statement

Hero has a string of lowercase English letters. Each letter that appears in the string appears exactly twice. Hero now wants to remove one half of his string. More precisely, he wants to remove one of the two copies of each letter in his string. The order of the letters he does not remove will remain unchanged. If there are multiple ways to remove the letters, Hero prefers the ones where the resulting string begins with a smaller letter (i.e., a letter that is earlier in the alphabet). You are given the String s containing Hero's string. Find the smallest letter that can appear at the beginning of the string after Hero removes half of the letters. Return a String with a single character: that letter.

Definition

Class:
StringHalving
Method:
lexsmallest
Parameters:
String
Returns:
String
Method signature:
String lexsmallest(String s)
(be sure your method is public)

Constraints

  • s will contain between 2 and 50 characters, inclusive.
  • Each character in s will be between 'a' and 'z', inclusive.
  • Each letter from 'a' to 'z' will have either zero or two occurrences in s.

Examples

  1. "baba"

    Returns: "a"

    Hero can remove the first 'b' and the second 'a' to obtain the string "ab".

  2. "bbaa"

    Returns: "b"

    Regardless of which 'a' and which 'b' Hero removes, the resulting string will always be "ba".

  3. "zyiggiyssz"

    Returns: "g"

  4. "topcodertpcder"

    Returns: "c"

  5. "rvofqorvfq"

    Returns: "f"

  6. "ppofofxlxltyty"

    Returns: "p"

  7. "qftbvfjmvcqzkbgmgtjzck"

    Returns: "b"

  8. "yckhtbgxpexorqidshtfuvakabynqdpluoslmvgjcmwijfnwre"

    Returns: "b"

  9. "guidmqbjgmujwbwqdi"

    Returns: "b"

  10. "qqozpnbneplybemlaawzomwy"

    Returns: "q"

  11. "yasfcovpfdkkybodusmmptveleulcabt"

    Returns: "a"

  12. "ijzyzynjbiccbn"

    Returns: "i"

  13. "whmfuymyfbczlcdjuvhzjpldpbvw"

    Returns: "f"

  14. "crfpuvzrfpizicuv"

    Returns: "c"

  15. "mowklbgjjwadbgoymfndnfkylhah"

    Returns: "b"

  16. "knpqqnepxhhebxbk"

    Returns: "k"

  17. "ulxzqohoqzhlxu"

    Returns: "h"

  18. "itqzrhfldhufjyewwmnrqlsyeuijtmadngbabzgs"

    Returns: "d"

  19. "zzoyywrwrmmo"

    Returns: "z"

  20. "qzyorujjpvxzhdosqsyndxunvphr"

    Returns: "j"

  21. "mualhqnhedrifvwitbbfpskqysalgxegjxjvocywctuorndpkm"

    Returns: "a"

  22. "rfwkutmsfcpyhbymeowsxudcqjqjelgkilgrdonathvpxinbva"

    Returns: "f"

  23. "siasrzcqzfwevhtwlxfcxvetrahlqi"

    Returns: "a"

  24. "cyctjtlmugjywwfevgmefvul"

    Returns: "c"

  25. "jbcycdyrrudjbtut"

    Returns: "b"

  26. "rwhrybvxcqyxhtnkfuvemodllskinjcqgpawpedoifuajsbmtg"

    Returns: "h"

  27. "nilonirolcergwkgweckff"

    Returns: "i"

  28. "mhvgizndzsrsulndvigeeaauflhmrfkk"

    Returns: "d"

  29. "ctnvosrwjhjevcwhmmuteosnru"

    Returns: "c"

  30. "bpaprglybvqfrzqvfgahlkzykh"

    Returns: "a"

  31. "idoemusszbevgppdyzvfkiaobgykxmuxaf"

    Returns: "d"

  32. "ncturvynjrwbvstbiouoycsjwi"

    Returns: "c"

  33. "wjafsohadozmypzwsjfhriidpymr"

    Returns: "a"

  34. "cfvatvyowpwbfjtgnsngaysojpcb"

    Returns: "a"

  35. "ptxyaijcblgcerfvswrwnhgdesplqfkhyuoukxjabniqmdovmt"

    Returns: "a"

  36. "yetjebmnfhmhwwfbpayrjnkptkar"

    Returns: "e"

  37. "rvoymfkawgyohijvtemdfbrpqxehagluqtswckcdnuljsnixpb"

    Returns: "a"

  38. "sqglpnexcwartchnufkrbjlmiotmgvsxbivpkouhqywdfadjey"

    Returns: "a"

  39. "axwvwqkvjtpgsohcladnxrlbmrsynjmhtebigdfcufiquoyepk"

    Returns: "a"

  40. "shvgqrrtgxlxdeamtiqkbmubcnpawydusyeolfjfjwkpovihnc"

    Returns: "g"

  41. "gtnjngxliqkiwjrtlkzzuquxrw"

    Returns: "g"

  42. "nhylxkxocjlarjfeunfytmkviusdcdqrpstweoiqbwvhbgpagm"

    Returns: "h"

  43. "anmbkijndbudfhxasiujmhxkfs"

    Returns: "a"

  44. "gtkanrvlppbahuurxzxjozjdgsthvblondsk"

    Returns: "a"

  45. "bzjfmjuxbrmaexafrzue"

    Returns: "b"

  46. "cdlcvbawosxydfhvyxginurhgfjaukirpseolpmjtnewbqqmkt"

    Returns: "c"

  47. "dlcofkvyckdlofvy"

    Returns: "c"

  48. "zndkwzusuakgelapgctcneldpwts"

    Returns: "d"

  49. "tajwqkntmqyjwmnaddyk"

    Returns: "a"

  50. "ivauwhaqomuefgypfrtxkjonqswclphilmsygtrdbjdcebkvxn"

    Returns: "a"

  51. "hxiykftetxshqzfobrmmslpokeryzilqbp"

    Returns: "e"

  52. "qfmmfddqnn"

    Returns: "f"

  53. "cwgtuztizvkpxdbdjogipjxbelkoeuvwlc"

    Returns: "c"

  54. "onoddn"

    Returns: "n"

  55. "duptlmjqnfkhuxbsyynkaccxwpihvajtgmewlrsebvorgiqodf"

    Returns: "d"

  56. "bbaacc"

    Returns: "b"

  57. "ddcc"

    Returns: "d"

  58. "bloobmlimnigng"

    Returns: "b"

  59. "zyzyaabbccddee"

    Returns: "y"

  60. "deecdc"

    Returns: "d"

  61. "cbcaba"

    Returns: "b"

  62. "bcbcaa"

    Returns: "b"

  63. "wxxw"

    Returns: "w"

  64. "cdbdbaca"

    Returns: "b"

  65. "cbcabazzwwqqeerrtt"

    Returns: "b"

  66. "zzaa"

    Returns: "z"

  67. "xbbaxa"

    Returns: "b"

  68. "cbcaab"

    Returns: "b"

  69. "zxcxbdcdbaaz"

    Returns: "c"

  70. "deedaa"

    Returns: "d"

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: