Function monotone_crescendo::solution::monotone_crescendo_prefix_sums

pub fn monotone_crescendo_prefix_sums(s: &str) -> i32

This is the official solution to LeetCode problem #926

The solution was simply translated by me into rust from java.

Explanation

I find the explanation on LeetCode to this solution somewhat overcomplicated and hard to understand, so I will attempt to explain it (hopefully) a bit simpler here.

The first thing this solution does is calculate the prefix sum of every item in the string and store it in an array. So for example, if we had the string 11010, the prefix sum array for that string would look like: [0,1,2,2,3,3]. This prefix sum array represents the the number of 1’s that are present before the corresponding character index in the string.

This solution then works by looping through the given string and, for each character in the string, analyzing the string as two halves partioned at that character. The number of 1’s in the first half are added to the number of 0’s in the second half to determine the total number of flips needed to make the string monotone increasing for that location in the string.

We get the number of 1’s in the first half by looking up the corresponding index in the prefix sum array. We get the number of 0’s in the second half by subtracting the number of 1’s in the second half from the length of the second half.

We then compare this number to the current minimum flips value and take the minimum of these two values again. The minimium we have in the end is what we return.

Note: the prefix sum array could also be optimized to remove the redundant element at index 0. The way the solution on LeetCode calculates the prefix sum array, the first element will always be zero. For example, if we had the string 11010, the prefix sum array could be optimized to [1,2,2,3,3]. Apparently the official solution calculates the prefix sum array with the redundant zero at the beginning to prevent some sort of possible overflow condition, out of principle more than anything else. See monotone_crescendo_prefix_sums_without_redundant_zero for an example.