maximum-manhattan-distance-after-all-moves

java

python3

python

javascript

typescript

csharp

golang

kotlin

swift

rust

ruby

dart

scala

elixir

erlang

racket

cangjie

bash

mysql

mssql

postgresql

oraclesql

pythondata

Count the net horizontal movement, net vertical movement, and the number of underscores.

Without underscores, the final distance is <code>abs(x) + abs(y)</code>.

Each underscore can always be chosen to increase the final Manhattan distance by 1, so add the number of underscores to the fixed-move distance.

Algorithms

You are given a string <code>moves</code> consisting of the characters <code>&#39;U&#39;</code>, <code>&#39;D&#39;</code>, <code>&#39;L&#39;</code>, <code>&#39;R&#39;</code>, and <code>&#39;_&#39;</code>.

Starting from the origin <code>(0, 0)</code>, each character represents one move on a 2D plane:

<ul>
	<li><code>&#39;U&#39;</code>: Move up by 1 unit.</li>
	<li><code>&#39;D&#39;</code>: Move down by 1 unit.</li>
	<li><code>&#39;L&#39;</code>: Move left by 1 unit.</li>
	<li><code>&#39;R&#39;</code>: Move right by 1 unit.</li>
	<li><code>&#39;_&#39;</code>: Can be independently replaced with any one of <code>&#39;U&#39;</code>, <code>&#39;D&#39;</code>, <code>&#39;L&#39;</code>, or <code>&#39;R&#39;</code>.</li>
</ul>

Return the maximum Manhattan distance from the origin that can be achieved after all moves have been performed.

&nbsp;
Example 1:

<div class="example-block">
Input: moves = &quot;L_D_&quot;

Output: 4

Explanation:

One optimal choice is:

<ul>
	<li><code>&#39;L&#39;</code>: <code>(0, 0) -&gt; (-1, 0)</code></li>
	<li><code>&#39;_&#39;</code> treated as <code>&#39;D&#39;</code>: <code>(-1, 0) -&gt; (-1, -1)</code></li>
	<li><code>&#39;D&#39;</code>: <code>(-1, -1) -&gt; (-1, -2)</code></li>
	<li><code>&#39;_&#39;</code> treated as <code>&#39;L&#39;</code>: <code>(-1, -2) -&gt; (-2, -2)</code></li>
</ul>

The final Manhattan distance from the origin is <code>|0 - (-2)| + |0 - (-2)| = 4</code>.
</div>

Example 2:

<div class="example-block">
Input: moves = &quot;U_R&quot;

Output: 3

Explanation:

One optimal choice is:

<ul>
	<li><code>&#39;U&#39;</code>: <code>(0, 0) -&gt; (0, 1)</code></li>
	<li><code>&#39;_&#39;</code> treated as <code>&#39;U&#39;</code>: <code>(0, 1) -&gt; (0, 2)</code></li>
	<li><code>&#39;R&#39;</code>: <code>(0, 2) -&gt; (1, 2)</code></li>
</ul>

The final Manhattan distance from the origin is <code>|0 - 1| + |0 - 2| = 3</code>.
</div>

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= moves.length &lt;= 105</code></li>
	<li><code>moves</code> consists of only <code>&#39;U&#39;</code>, <code>&#39;D&#39;</code>, <code>&#39;L&#39;</code>, <code>&#39;R&#39;</code>, and <code>&#39;_&#39;</code>.</li>
</ul>

第 507 场周赛

weekly-contest-507

maxDistance

高级工程师

Maximum Manhattan Distance After All Moves

Maximum Manhattan Distance After K Changes

maximum-manhattan-distance-after-k-changes

K 次修改后的最大曼哈顿距离

Math

String

Counting

给你一个由字符 <code>'U'</code>、<code>'D'</code>、<code>'L'</code>、<code>'R'</code> 和 <code>'_'</code> 组成的字符串 <code>moves</code>。

从原点 <code>(0, 0)</code> 出发，每个字符表示二维平面上的一次移动：

<ul>
	<li><code>'U'</code>：向上移动 1 个单位。</li>
	<li><code>'D'</code>：向下移动 1 个单位。</li>
	<li><code>'L'</code>：向左移动 1 个单位。</li>
	<li><code>'R'</code>：向右移动 1 个单位。</li>
	<li><code>'_'</code>：可以独立地替换为 <code>'U'</code>、<code>'D'</code>、<code>'L'</code> 或 <code>'R'</code> 中的任意一个字符。</li>
</ul>

返回执行完所有移动后，能够达到的距离原点的&nbsp;最大曼哈顿距离&nbsp;。

两点 <code>(x1, y1)</code> 和 <code>(x2, y2)</code> 之间的&nbsp;曼哈顿距离&nbsp;为 <code>|x1 - x2| + |y1 - y2|</code>。

&nbsp;

示例 1：

<div class="example-block">
输入： moves = "L_D_"

输出： 4

解释：

一种最优选择为：

<ul>
	<li><code>'L'</code>：<code>(0, 0) -&gt; (-1, 0)</code></li>
	<li>将 <code>'_'</code> 视为 <code>'D'</code>：<code>(-1, 0) -&gt; (-1, -1)</code></li>
	<li><code>'D'</code>：<code>(-1, -1) -&gt; (-1, -2)</code></li>
	<li>将 <code>'_'</code> 视为 <code>'L'</code>：<code>(-1, -2) -&gt; (-2, -2)</code></li>
</ul>

最终位置到原点的曼哈顿距离为 <code>|0 - (-2)| + |0 - (-2)| = 4</code>。
</div>

示例 2：

<div class="example-block">
输入： moves = "U_R"

输出： 3

解释：

一种最优选择为：

<ul>
	<li><code>'U'</code>：<code>(0, 0) -&gt; (0, 1)</code></li>
	<li>将 <code>'_'</code> 视为 <code>'U'</code>：<code>(0, 1) -&gt; (0, 2)</code></li>
	<li><code>'R'</code>：<code>(0, 2) -&gt; (1, 2)</code></li>
</ul>

最终位置到原点的曼哈顿距离为 <code>|0 - 1| + |0 - 2| = 3</code>。
</div>

&nbsp;

提示：

<ul>
	<li><code>1 &lt;= moves.length &lt;= 105</code></li>
	<li><code>moves</code> 仅由 <code>'U'</code>、<code>'D'</code>、<code>'L'</code>、<code>'R'</code> 和 <code>'_'</code> 组成。</li>
</ul>