Bob is currently at point ($0,0$) in the infinite 2D plane, he is going to move $n$ steps, each step is either up, down, left or right. After finishing, he will repeat those exact $n$ steps again and again and again and agai... until he wants to move between two points that he already moved between before. For example, if the $n$ steps are up, right then down, he will start at point ($0,0$) go up to point ($0,1$) then go right to point ($1,1$) then go down to point ($1,0$), then he will want to repeat the $n$ steps and go up, right then down again, so he first tries to go up, but he already moved between the two points ($1,0$) and ($1,1$), so he stops at the $4^{th}$ step.
You're given the $n$ steps, print the number of the step that he will stop at or 1
if he will never stop. It's guaranteed that if he will stop, then the answer will not be greater than $10^{18}$.
The input contains a single string of length $n$($1 \le n \le 10^6$) consisting of the characters UDLR
.
Print a single integer, the answer as specified above.
Input  Output 

URDR Copy

1 Copy

URRULDDL Copy

9 Copy

LR Copy

2 Copy

Firstly separate vertical and horizontal steps since they can't collide with each other.
Let $d$ be the point Bob will stand at after doing $n$ steps and let's look at a single step of one of the first $n$ steps, let's say the step between point $p$ and point ($p_x + 1, p_y$), another step will be taken after $n$ steps between point ($p_x + d_x, p_y + d_y$) and ($p_x + 1 + d_x, p_y + d_y$), after another $n$ steps a step between points ($p_x + 2d_x, p_y + 2d_y$) and ($p_x + 1 + 2d_x, p_y + 2d_y$) will be taken, and so on.
Let's call step $i$, $i+n$, $i+2n$ and so on as step of type $i$ for $1 \le i \le n$, and let's say that a step of type $i$ will eventually collide with a step of type $j$, then every step of type $j$ will eventually collide with every type that a step of type $i$ has collided with, and only those types, so we can put all types into groups, such that every pair of types in the same group will eventually collide together.
After that, for each group, let's check all pairs and see how much time is needed for them to collide and update answer accordingly, but this will result in $O(n^2)$ solution, but we don't need to check all pairs, instead we can for each type look at the first step for that type, then sort them in the direction of $d$(seen as a vector) and only check adjacent steps.
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define f(i, x, n) for(int i = x; i < (int)(n); ++i)
ll const inf = 1e18;
int const N = 1000000;
int n;
char s[N + 1];
ll an = inf;
int sg(int v){
return v < 0 ? 1 : 1;
}
struct P{
int x, y;
P():x(0), y(0) {}
P(int a, int b):x(a), y(b) {}
bool operator <(P const &o)const {
if (x == o.x)return y < o.y;
return x < o.x;
}
bool operator ==(P const &o)const { return x == o.x && y == o.y; }
P operator *(int s)const { return P(x * s, y * s); }
P operator +(P const &o)const { return P(x + o.x, y + o.y); }
P operator (P const &o)const { return P(x  o.x, y  o.y); }
P go(char c){
switch (c){
case 'U': return P(x, y + 1);
case 'D': return P(x, y  1);
case 'R': return P(x + 1, y);
default: return P(x  1, y);
}
}
int dis(P const &o, P const &d)const {
if (x == o.x){
if (y == o.y)return 0;
return abs(y  o.y) / abs(d.y);
}
return abs(x  o.x) / abs(d.x);
}
P N(P const &d)const {
P an = *this;
if (d.x == 0){
if (d.y == 0)return an;
int t = this>y / d.y;
an = an  d * t;
if (an.y < 0)an = an + (d * sg(d.y));
}else {
int t = this>x / d.x;
an = an  d * t;
if (an.x < 0)an = an + (d * sg(d.x));
}
return an;
}
void pr() { printf("%d %d\n", x, y); }
}d;
void up(vector<pair<P, int> > &v){
sort(v.begin(), v.end());
if (d.x < 0  (d.x == 0 && d.y < 9))reverse(v.begin(), v.end());
f(i, 1, v.size()){
int dis = v[i  1].first.dis(v[i].first, d);
if (dis == 0)an = min(an, (ll)max(v[i  1].second, v[i].second));
else {
an = min(an, v[i  1].second + (ll)dis * n);
}
}
}
int main(){
scanf("%s", s);
n = strlen(s);
f(i, 0, n)d = d.go(s[i]);
map<P, vector<pair<P, int> > > hm, vm;
P p;
f(i, 0, n){
P t = p;
p = p.go(s[i]);
if (p < t)t = p;
if (s[i] == 'L'  s[i] == 'R'){
hm[t.N(d)].emplace_back(t, i + 1);
}else {
vm[t.N(d)].emplace_back(t, i + 1);
}
}
for (auto it = hm.begin(); it != hm.end(); ++it)up(it>second);
for (auto it = vm.begin(); it != vm.end(); ++it)up(it>second);
if (d.x == 0 && d.y == 0)an = min(an, n + 1ll);
printf("%lld\n", an == inf ? 1 : an);
}