Loading...
Loading...
Loading...
Priya is setting up a light strip for the hostel Diwali night. Each bulb has a colour code, a lowercase letter, so the strip reads like a word. She thinks the strip may be one short block of colours repeated end to end, like rgb + rgb + rgb.
Check whether the strip s can be made by writing some shorter block two or more times in a row. If it can, print the shortest such block and how many times it is written.
YES on the first line, and the shortest such block and k, separated by a space, on the second line. Otherwise print only NO.Example 1
Input
rgbrgbrgb
Output
YES rgb 3
rgb written 3 times gives the strip. No 1-letter block works.
Example 2
Input
rgbrg
Output
NO
A block of 3 letters cannot fill 5 bulbs exactly, and no other block works either.
Try the problem first. Open one hint at a time.
A block length must divide the length of s exactly, and the block must be shorter than s.
Think about the longest proper prefix of s that is also a suffix of s.
If that length is b and n is the length of s, then p = n − b is the shortest period of s.
s is a repeated block exactly when p < n and n is divisible by p. Then the block is the first p letters and k = n / p.
Write your Java code, run it on the examples and submit it to hidden tests.
Solve in the editor