{"raw_statement":[{"iden":"statement","content":"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.\n\nIn 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.\n\nThe first line of input is n (1 ≤ n ≤ 106), the length of the string of snake moves. \n\nThe second line contains the string of snake moves where each character is in the set {'L', 'R', 'U', 'D'}.\n\nOutput 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.\n\n"},{"iden":"input","content":"The 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'}."},{"iden":"output","content":"Output 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."},{"iden":"examples","content":"Input4\nRULD\nOutput3\nInput13\nRRDDLLUUURDDR\nOutput10\nInput3\nRRU\nOutput3\nInput2\nRL\nOutput1\n"}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ s \\in \\{ \\text{L}, \\text{R}, \\text{U}, \\text{D} \\}^n $ be a string of length $ n $, representing a sequence of moves.  \nLet $ p: \\{0, \\dots, n\\} \\to \\mathbb{Z}^2 $ be the position function, where $ p(0) = (0,0) $, and for $ i \\geq 1 $:  \n- $ p(i) = p(i-1) + \\vec{v}(s_i) $,  \nwith $ \\vec{v}(\\text{L}) = (-1, 0) $, $ \\vec{v}(\\text{R}) = (1, 0) $, $ \\vec{v}(\\text{U}) = (0, 1) $, $ \\vec{v}(\\text{D}) = (0, -1) $.\n\n**Constraints**  \n$ 1 \\leq n \\leq 10^6 $\n\n**Objective**  \nFind the maximum length $ \\ell $ such that there exists a substring $ s[i:j] $ (with $ 0 \\leq i < j \\leq n $) of length $ \\ell = j - i $, for which all positions $ p(i), p(i+1), \\dots, p(j) $ are distinct.  \nThat is, maximize $ \\ell = j - i $ subject to:  \n$$\n\\left| \\{ p(k) \\mid k \\in \\{i, i+1, \\dots, j\\} \\} \\right| = j - i + 1\n$$","simple_statement":"Find the longest substring of moves where the snake never visits the same cell twice.","has_page_source":false}