An orchard keeper tends a single straight row of n plots, each currently either dormant or blooming. The state of the row is given as a string of the characters '0' (dormant) and '1' (blooming), read from the western end of the row to the eastern end. The keeper wants to build exactly one dividing fence strictly between two neighbouring plots, splitting the row into a non-empty western section (every plot to the left of the fence) and a non-empty eastern section (every plot to the right of the fence). For a given fence placement, the resulting harmony score is the number of dormant plots in the western section plus the number of blooming plots in the eastern section. Find the maximum harmony score achievable over every valid fence placement.
Example 1
Input
00110
Expected
4
Explanation
The row is "00110" (n=5). Trying every fence position p from 1 to 4: p=2 gives western section "00" (2 dormant plots) and eastern section "110" (2 blooming plots), for a harmony score of 2+2=4, which beats p=1 (1+2=3), p=3 (2+1=3), and p=4 (2+0=2). The answer is 4.
Example 2
Input
111000
Expected
2
Explanation
The row is "111000" (n=6). Checking every fence position: p=1 gives western "1" (0 dormant) and eastern "11000" (2 blooming) for a score of 2; p=5 gives western "11100" (2 dormant) and eastern "0" (0 blooming) for a score of 2. Positions p=2,3,4 all score lower (1, 0, and 1 respectively). No position beats 2, so the answer is 2.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →