Let $ s \in \{L, R, U, D\}^n $ be a string of length $ n = |s| $, where each character represents a unit step in one of four directions:
- $ L $: $ (-1, 0) $
- $ R $: $ (1, 0) $
- $ U $: $ (0, 1) $
- $ D $: $ (0, -1) $
Let $ x $ and $ y $ denote the net displacement in the horizontal and vertical directions, respectively, after following the entire string $ s $. Define:
- $ c_R $: count of $ R $ in $ s $
- $ c_L $: count of $ L $ in $ s $
- $ c_U $: count of $ U $ in $ s $
- $ c_D $: count of $ D $ in $ s $
Then:
$$
x = c_R - c_L, \quad y = c_U - c_D
$$
Memory may change any character in $ s $ to any of $ \{L, R, U, D\} $. Each change alters the displacement by at most 1 unit in one coordinate.
Let $ \Delta x = -x $, $ \Delta y = -y $ be the required net correction to reach the origin.
Each edit can adjust $ x $ by $ \pm 1 $ (by changing $ L \leftrightarrow R $) or $ y $ by $ \pm 1 $ (by changing $ U \leftrightarrow D $), or change a step in one axis to the other axis (e.g., $ R \to U $), which adjusts both $ x $ and $ y $ simultaneously.
Let $ a = c_R + c_L $, $ b = c_U + c_D $, so $ a + b = n $.
We wish to find the **minimum number of edits** to make the final displacement $ (0, 0) $.
Let $ r = c_R $, $ l = c_L $, $ u = c_U $, $ d = c_D $. Then:
$$
x = r - l, \quad y = u - d
$$
We need:
$$
r' - l' = 0, \quad u' - d' = 0
$$
where $ r' + l' + u' + d' = n $, and $ r', l', u', d' \geq 0 $ are integers.
Let $ \delta_x = r - l $, $ \delta_y = u - d $. We must correct $ \delta_x $ and $ \delta_y $ to 0.
Each edit can:
1. Change $ R \leftrightarrow L $: changes $ \delta_x $ by $ \pm 2 $
2. Change $ U \leftrightarrow D $: changes $ \delta_y $ by $ \pm 2 $
3. Change $ R \leftrightarrow U $, $ R \leftrightarrow D $, $ L \leftrightarrow U $, $ L \leftrightarrow D $: changes $ \delta_x $ and $ \delta_y $ each by $ \pm 1 $, in some combination.
Let $ k $ be the number of edits.
We want to minimize $ k $ such that there exist non-negative integers $ a, b, c, d $ with $ a + b + c + d = k $, where:
- $ a $: number of $ R \leftrightarrow L $ swaps (each changes $ \delta_x $ by $ \pm 2 $)
- $ b $: number of $ U \leftrightarrow D $ swaps (each changes $ \delta_y $ by $ \pm 2 $)
- $ c $: number of axis-crossing edits (e.g., $ R \to U $, etc.) — each such edit can adjust $ \delta_x $ and $ \delta_y $ by $ \pm 1 $, independently
But note: an axis-crossing edit can correct one unit of $ \delta_x $ and one unit of $ \delta_y $ simultaneously.
Let $ dx = |\delta_x| $, $ dy = |\delta_y| $. We need to reduce $ dx $ and $ dy $ to 0.
Each $ R \leftrightarrow L $ edit can reduce $ dx $ by 2 (if applied to excess $ R $ or $ L $).
Each $ U \leftrightarrow D $ edit can reduce $ dy $ by 2.
Each axis-crossing edit (e.g., changing an excess $ R $ to $ D $) can reduce $ dx $ by 1 and $ dy $ by 1, or $ dx $ by 1 and increase $ dy $ by 1, etc. — we can choose the direction to reduce both.
So the optimal strategy is:
- Use axis-crossing edits to correct as much as possible of both $ dx $ and $ dy $ simultaneously.
- Then use same-axis swaps to correct the remaining even differences.
Let $ m = \min(dx, dy) $. Then we can use $ m $ axis-crossing edits to reduce both $ dx $ and $ dy $ by $ m $, leaving $ dx' = dx - m $, $ dy' = dy - m $.
Then we need to correct $ dx' $ and $ dy' $, which are now non-negative and one of them is 0.
The remaining correction is $ dx' + dy' $, and since both are even (because $ dx - m $ and $ dy - m $ are both even or both odd? Not necessarily — wait, parity matters).
Actually, note: the total displacement $ dx + dy $ has a parity constraint.
Each edit changes the total displacement vector by a vector of $ \ell_1 $-norm 1 or 2.
But observe: the **parity** of $ dx + dy $ modulo 2 is invariant under same-axis swaps (they change $ dx $ or $ dy $ by $ \pm 2 $, so parity of $ dx + dy $ unchanged), and under axis-crossing edits: changing $ R \to U $, for example, decreases $ dx $ by 1 and increases $ dy $ by 1 → $ dx + dy $ unchanged. Similarly, any axis-crossing edit changes $ dx $ and $ dy $ by $ \pm 1 $ in opposite directions, so $ dx + dy $ remains unchanged modulo 2.
Therefore, $ dx + dy \mod 2 $ is invariant under all edits.
But we need $ dx + dy = 0 $, so if the initial $ dx + dy $ is odd, it is **impossible**.
Wait: we need final $ dx = 0 $, $ dy = 0 $, so $ dx + dy = 0 $, even.
So if $ (c_R - c_L) + (c_U - c_D) \not\equiv 0 \pmod{2} $, then impossible.
But actually, that’s not the right invariant. The invariant is the **parity of the total displacement vector**, but we care about whether we can reach (0,0).
Actually, the key invariant is: **the parity of $ n $**.
Each step is one unit. After $ n $ steps, to return to origin, the total displacement is zero, so the number of steps must be even? No — for example, 2 steps: R then L → 0, even. But 1 step: can’t return. In fact, to return to origin, the number of steps must be even, because each step is ±1 in one coordinate, so to cancel, you need even number of steps in each axis.
More precisely: to have $ r = l $ and $ u = d $, then $ r + l + u + d = n $ must be even, because $ r + l = 2r $, $ u + d = 2u $, so $ n = 2(r + u) $, even.
Therefore, **necessary condition**: $ n $ must be even.
If $ n $ is odd, output $-1$.
If $ n $ is even, then we can attempt to fix.
Now, we need to make $ r' = l' $, $ u' = d' $, so total steps per axis must be even.
Let $ a = r + l $, $ b = u + d $, $ a + b = n $, even.
We need $ r' = l' = a'/2 $, $ u' = d' = b'/2 $, so $ a' $ and $ b' $ must be even.
But we can change steps between axes.
Let $ r $, $ l $, $ u $, $ d $ be current counts.
We want to choose non-negative integers $ r', l', u', d' $ such that:
- $ r' + l' + u' + d' = n $
- $ r' = l' $
- $ u' = d' $
- Minimize the number of changes: $ \frac{1}{2} \left( |r - r'| + |l - l'| + |u - u'| + |d - d'| \right) $
But since $ r' = l' $, $ u' = d' $, let $ r' = l' = x $, $ u' = d' = y $, then $ 2x + 2y = n \Rightarrow x + y = n/2 $.
We need to choose $ x, y \geq 0 $, integers, $ x + y = n/2 $, to minimize:
$$
\frac{1}{2} \left( |r - x| + |l - x| + |u - y| + |d - y| \right)
$$
But note: $ r + l = a $, $ u + d = b $, $ a + b = n $.
We can rewrite the cost as:
$$
\text{cost}(x) = \frac{1}{2} \left( |r - x| + |l - x| + |u - (n/2 - x)| + |d - (n/2 - x)| \right)
$$
Let $ f(x) = |r - x| + |l - x| + |u - (n/2 - x)| + |d - (n/2 - x)| $
We want to minimize $ f(x) $ over integers $ x \in [0, n/2] $.
Note that $ |r - x| + |l - x| $ is minimized when $ x $ is between $ r $ and $ l $, and equals $ |r - l| $ if $ x \in [\min(r,l), \max(r,l)] $, but actually:
The function $ |r - x| + |l - x| $ is minimized at any $ x $ in $ [\min(r,l), \max(r,l)] $, and the minimum value is $ |r - l| $.
Similarly, $ |u - y| + |d - y| $ with $ y = n/2 - x $ is minimized when $ y \in [\min(u,d), \max(u,d)] $, and minimum value $ |u - d| $.
But we are constrained by $ y = n/2 - x $.
So we have:
Let $ dx = |r - l| $, $ dy = |u - d| $
Then $ f(x) \geq dx + dy $, and equality holds if $ x \in [\min(r,l), \max(r,l)] $ and $ n/2 - x \in [\min(u,d), \max(u,d)] $
That is, if the intervals $ [\min(r,l), \max(r,l)] $ and $ [n/2 - \max(u,d), n/2 - \min(u,d)] $ overlap.
But perhaps a simpler way:
We need to correct the imbalance.
Let $ \delta_x = r - l $, $ \delta_y = u - d $
We need to make $ \delta_x = 0 $, $ \delta_y = 0 $
Each edit can:
- Change an $ R $ to $ L $: $ \delta_x \leftarrow \delta_x - 2 $
- Change an $ L $ to $ R $: $ \delta_x \leftarrow \delta_x + 2 $
- Change a $ U $ to $ D $: $ \delta_y \leftarrow \delta_y - 2 $
- Change a $ D $ to $ U $: $ \delta_y \leftarrow \delta_y + 2 $
- Change an $ R $ to $ U $: $ \delta_x \leftarrow \delta_x - 1 $, $ \delta_y \leftarrow \delta_y + 1 $
- Change an $ R $ to $ D $: $ \delta_x \leftarrow \delta_x - 1 $, $ \delta_y \leftarrow \delta_y - 1 $
- Similarly for $ L \to U $, $ L \to D $, etc.
So we can model this as: we have two integers $ \delta_x, \delta_y $, and we can apply operations:
- Type A: $ (\pm 2, 0) $
- Type B: $ (0, \pm 2) $
- Type C: $ (\pm 1, \pm 1) $ — four variants
We want the minimum number of operations to reach $ (0,0) $.
Let $ a = |\delta_x| $, $ b = |\delta_y| $
We can use Type C operations to reduce both $ a $ and $ b $ simultaneously.
Each Type C reduces $ a $ and $ b $ by 1, but only if we choose the correct sign.
So we can use $ m = \min(a, b) $ Type C operations to reduce both to $ a - m $, $ b - m $.
Then we are left with $ a' = a - m $, $ b' = b - m $, one of which is 0.
Say $ a' > 0 $, $ b' = 0 $. Then we need to reduce $ a' $ to 0 using Type A operations, each of which reduces by 2.
So we need $ \lceil a' / 2 \rceil $ operations? But since $ a' $ is even? Not necessarily.
Wait: what is the parity?
Note: each operation changes $ \delta_x + \delta_y $ by:
- Type A: $ \pm 2 $ → parity of $ \delta_x + \delta_y $ unchanged
- Type B: $ \pm 2 $ → unchanged
- Type C: $ \pm 1 \pm 1 $ → $ \pm 2 $, 0, or $ \pm 2 $ → always even change
So $ \delta_x + \delta_y \mod 2 $ is invariant.
Initially, $ \delta_x + \delta_y = (r - l) + (u - d) $
Final: 0.
So if $ (r - l) + (u - d) \not\equiv 0 \pmod{2} $, then impossible.
But also, since total steps $ n = r + l + u + d $, and we need $ r' = l' $, $ u' = d' $, so $ r' + l' + u' + d' = 2(r' + u') = n $, so $ n $ must be even.
So necessary conditions:
1. $ n $ even
2. $ (r - l) + (u - d) \equiv 0 \pmod{2} $
But $ (r - l) + (u - d) = (r + u) - (l + d) $, and since $ r + l + u + d = n $, then $ (r + u) - (l + d) = 2(r + u) - n $, so $ 2(r + u) - n \equiv 0 \pmod{2} $ → always true if $ n $ even.
So only condition: **n must be even**.
If $ n $ is odd → impossible → output -1.
If $ n $ is even, then we can always fix it.
Now, how many edits?
Let $ \delta_x = r - l $, $ \delta_y = u - d $
We need to reduce $ |\delta_x| $ and $ |\delta_y| $ to 0.
Let $ a = |\delta_x| $, $ b = |\delta_y| $
We can use $ m = \min(a, b) $ axis-crossing edits (Type C) to reduce both by $ m $, leaving $ a' = a - m $, $ b' = b - m $
Then we need to reduce $ a' $ and $ b' $, one of which is 0.
Say $ a' > 0 $, $ b' = 0 $. Then we need $ a' / 2 $ same-axis edits (Type A), since each changes $ \delta_x $ by $ \pm 2 $.
Similarly if $ b' > 0 $.
So total edits: $ m + \frac{a'}{2} + \frac{b'}{2} = \min(a,b) + \frac{|a - b|}{2} = \frac{a + b}{2} $
Because $ \min(a,b) + \frac{|a - b|}{2} = \frac{2 \min(a,b) + |a - b|}{2} = \frac{ \max(a,b) + \min(a,b) }{2} = \frac{a + b}{2} $
So the minimum number of edits is $ \frac{ |\delta_x| + |\delta_y| }{2} $
But $ |\delta_x| + |\delta_y| = |r - l| + |u - d| $
And since $ n $ is even, this is always an integer? Not necessarily — but $ |\delta_x| + |\delta_y| $ is even because $ \delta_x + \delta_y \equiv 0 \pmod{2} $, and $ \delta_x - \delta_y \equiv 0 \pmod{2} $? Not necessarily.
Wait: $ \delta_x = r - l $, $ \delta_y = u - d $
$ \delta_x + \delta_y = (r + u) - (l + d) $
$ \delta_x - \delta_y = (r - u) - (l - d) $
But we know $ r + l + u + d = n $ even.
But $ \delta_x + \delta_y = (r + u) - (l + d) = 2(r + u) - n $, which is even since $ n $ even.
So $ \delta_x + \delta_y $ even → $ \delta_x \equiv \delta_y \pmod{2} $
Therefore $ |\delta_x| \equiv |\delta_y| \pmod{2} $, so $ |\delta_x| + |\delta_y| $ even → divisible by 2.
Thus, minimum edits = $ \frac{ |r - l| + |u - d| }{2} $
**Final Answer:**
If $ |s| $ is odd → output $-1$
Else → output $ \frac{ |(\text{count of } R) - (\text{count of } L)| + |(\text{count of } U) - (\text{count of } D)| }{2} $
In code:
```python
s = input().strip()
n = len(s)
if n % 2 == 1:
print(-1)
else:
c = {'L': 0, 'R': 0, 'U': 0, 'D': 0}
for char in s:
c[char] += 1
dx = c['R'] - c['L']
dy = c['U'] - c['D']
print((abs(dx) + abs(dy)) // 2)
```