Patching the Fence

Easy

A fence is described by the string fence, one character per board: 'X' is a broken board and 'O' is a sound one. A single patch covers exactly three adjacent boards and makes all of them sound; covering boards that are already fine is allowed. Return the smallest number of patches that leaves the whole fence sound.

Example 1

fence="OXXOOOXO" → 2

One patch covers boards 1–3 and a second covers boards 5–7.

Example 2

fence="XOOOX" → 2

Broken boards 0 and 4 are too far apart for a single patch.

Example 3

fence="OOO" → 0

Nothing to fix.

Constraints

3 ≤ len(fence) ≤ 1000
Every character of fence is 'X' or 'O'

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Greedy String

Similar problems

Palindrome From Letter Tiles Easy Palindrome With One Eraser Stroke Easy Rise and Fall Lineup Easy Most Even L/R Pieces Easy Time Behind the Smudges Easy

Input

fence="OXXOOOXO"

Expected

Run checks the first 3 tests in your browser. Submit checks all 169 tests on the server, hidden ones included.