405954: GYM102191 E Snake Moves
Description
You are playing the classical snake game on your phone, where a snake moves around on an infinite grid. However in this game, the snake has been programmed with a series of moves represented as a string. The characters 'U', 'D', 'L', and 'R' in the string cause the snake to move up, down, left, and right, respectively. The snake cannot visit the same cell twice in fear of colliding with itself.
In this version of the game, you want to find out the longest substring of the string of moves such that the snake never visits the same cell twice.
InputThe first line of input is n (1 ≤ n ≤ 106), the length of the string of snake moves.
The second line contains the string of snake moves where each character is in the set {'L', 'R', 'U', 'D'}.
OutputOutput a single line with the length of the longest substring of moves such that the snake would not visit the same cell twice if it followed those moves.
ExamplesInput4 RULDOutput
3Input
13 RRDDLLUUURDDROutput
10Input
3 RRUOutput
3Input
2 RLOutput
1