Problem · Greedy

Good Binary Strings

Learn this problem
HardBNPOA

Problem statement

Two definitions follow:

  • A binary string consists of 0s and/or 1s. For example, 01011, 1111, and 00 are binary strings.
  • The prefix of a string is any of its substrings that include the beginning of the string. For example, the prefixes of 11010 are 1, 11, 110, 1101, and 11010.
  • A non-empty binary string is good if the following two conditions are true:

  • The number of 0s is equal to the number of 1s.
  • For every prefix of the binary string, the number of 1s is not less than the number of 0s.
  • For example, 11010 is not good because it does not have an equal number of 0s and 1s, but 110010 is good because it satisfies both conditions.

    A good string can contain multiple good substrings. If two consecutive substrings are good, then they can be swapped as long as the resulting string is still a good string. Given a good binary string, binString, perform zero or more swap operations on its adjacent good substrings such that the resulting string is the largest possible numeric value. Two substrings are adjacent if the last character of the first substring occurs exactly one index before the first character of the second substring.

    Function

    largestGood(binString: String) → String

    Complete the function largestGood in the editor.

    largestGood has the following parameter(s):

    • String binString: a binary string

    Returns

    String: the largest possible good binary string

    Examples

    Example 1

    binString = "1010111000"return = "1110001010"

    The substrings 1010 and 111000 are both good. Swapping them produces 1110001010, the largest possible good binary string.

    More BNP problems

    drafts saved locally
    public String largestGood(String binString) {
      // write your code here
    }
    
    binString"1010111000"
    expected"1110001010"
    checking account