Minimum Spells to Revive Plants

You are given a garden represented by a string. Each character in the string is either an 'A' (alive plant) or a 'D' (dead plant). A magic spell is used to revive a continuous group of dead plants (i.e., a contiguous sequence of 'D's). Your task is to determine the minimum number of spells required to revive all the dead plants in the garden.

Note that each spell can revive a continuous segment of dead plants. For example, if the input is "DAAAD", applying one spell to the first 'D' and one spell to the last 'D' will revive all dead plants, so the answer is 2.

The problem can be stated mathematically as: Given a string \( S \) consisting of characters \( 'A' \) and \( 'D' \), find the number of contiguous segments composed solely of \( 'D' \). This is equivalent to computing the minimum number of spells \( k \) such that every \( 'D' \) is included in some segment.

inputFormat

The input is provided via standard input (stdin) and consists of a single line containing a non-negative string garden which comprises only the characters 'A' and 'D'.

If the input string is empty, it means the garden has no plants.

outputFormat

Print a single integer to standard output (stdout) representing the minimum number of spells required to revive all the dead plants in the garden.

DAAAD

2