Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Konami Code

By hjr265 · Limits 1s, 512 MB

The Konami code is a sequence of key/button presses that is implemented in many video games to unlock hidden features (and often act as a cheat code).

The Konami Code was created by Kazuhisa Hashimoto, who was developing the home port of the 1985 arcade game Gradius, a scrolling shooter released on the NES in 1986. Finding the game too difficult to play through during testing, he created a cheat code to give the player a full set of power-ups (normally attained gradually throughout the game). — Wikipedia

The key sequence goes something like this:


You could represent it as:


Here, U represents the up key, D represents the down key, L represents the left key, R represents the right key, and A and B represents the two action buttons found on NES controllers.

The Konami code is more popular than you may think. It has been found in many non-Konami video games, popular culture, and even in websites to unlock cool hidden features. In fact, you would be surprised to know that this is implemented in many of your favorite websites.

In this problem, you will have to write a program that will take a stream of key presses (each key press represented with one of the following characters: U, D, L, R, A, and B) and print the number of time the Konami code appears.

A Konami code is valid only if the following key press sequence occurs exactly in the stream:



The input will contain a single line of string composed of these characters only: U, D, L, R, A, and B. No other characters will appear in the string. The string will be at most 10000 characters in length.


Print a single integer representing the number of times the Konami code appears in the string.