PWC 342 Max Score: All Your 0s and 1s Are Belong to Us

#devchallenge #algorithms #performance #programming

Task 2: Max Score

Description

You are given a string, $str, containing 0 and 1 only.

Write a script to return the max score after splitting the string into two non-empty substrings. The score after splitting a string is the number of zeros in the left substring plus the number of ones in the right substring.

Example 1

Input: $str = "0011"
Output: 4
- 1: left = "0", right = "011" => 1 + 2 => 3
- 2: left = "00", right = "11" => 2 + 2 => 4
- 3: left = "001", right = "1" => 2 + 1 => 3

Thoughts

Evaluating the score at each possible partition point seems like too many compute cycles. There must be a way to do it in one pass, no?

Suppose we take the first possible partition, where there's one element on the left, and all the rest on the right. The "left" score is either 0 or 1, and the "right" score is the total number of 1s, minus possibly the first element.

Now let's move each element from the right to the left. If it's a 1, that reduces the score of "right", and contributes nothing to "left". If it's a 0, that adds one to the "left", and changes nothing for "right".

The last element from the right set won't shift to the left, because we are required to have non-empty substrings.

Let's go to the code

sub score($str)
{
    use List::Util qw/sum/;
    my @b = split(//, $str);
    my $right = sum(@b) - $b[0];
    my $left = (shift(@b) == 0 ? 1 : 0);
    pop(@b);
    my $best = $left + $right;

    for ( @b )
    {
        if ( $_ ) { $right-- } else { $left++ }
        my $s = $left + $right;
        $best = $s if $s > $best;
    }
    return $best;
}

Notes

@b = split(//, $str) -- create a list of 0s and 1s
$right = sum(@b) - $b[0] -- The initial split is to put b[0] on the left, and the rest on the right.
$left = (shift(@b) == 0 ? 1 : 0) -- The initial score for the left is the inverse of that bit. We are also removing it from further consideration with shift.
pop(@b) -- The right-most element will always be in the right split, and we've already counted it, so remove it from further consideration.
$best = $left + $right -- This is the best possible score so far.
for (@b) -- now pretend to move each bit from the right set into the left.
if ( $_ ) { $right-- } else { $left++ } -- As above, adjust the scores of the left and right side. Moving a one from right to left reduces the $right score; moving a zero increases the $left score.