Woburn Challenge 2018-19 Finals Round - Junior Division
Problem 2: Script Doctor
The Head Monkey has just completed her first draft of the film script, and has proudly passed it on to Bo Vine for a readthrough. Unfortunately, Bo has concerns that coarse language in the script might cause the movie to end up with an R rating, which would be a disaster! In order to secure exposure of the movie to younger audiences, he'd like to take a pass over the script himself to ensure that it contains no occurrences of a particularly offensive word: "
The script is a non-empty string S consisting of at most 1000 characters, each of which is either a lowercase letter ("
z") or an underscore ("
_"). Bo Vine would like to alter it as little as possible such that, once he's done, the string contains no occurrences of the substring "
bull". Now, he's not a writer, so he doesn't feel qualified to add anything to the script to accomplish his goal — he'll only remove existing characters from it.
Help Bo Vine remove as few characters as possible from S to yield a string with no occurrences of the substring "
bull". If there are multiple ways to do so, any will do. It's possible that no characters may need to be removed.
The first and only line of input consists of a single string, S.
Output a single string, any maximum-length cut-down version of S with no occurrences of "
Upon removing two characters (the 7th one, "
l", and the 22nd one, "
b"), the resulting string no longer contains "
bull". It's impossible to achieve this by only removing one character. Note that multiple other outputs with two removed characters would also be accepted.
Point Value: 5 (partial)
Time Limit: 2.00s
Memory Limit: 16M
Added: May 18, 2019
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3