change-minimum-characters-to-satisfy-one-of-three-conditions

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

You are given two strings <code>a</code> and <code>b</code> that consist of lowercase letters. In one operation, you can change any character in <code>a</code> or <code>b</code> to any lowercase letter.

Your goal is to satisfy one of the following three conditions:

<ul>
	<li>Every letter in <code>a</code> is strictly less than every letter in <code>b</code> in the alphabet.</li>
	<li>Every letter in <code>b</code> is strictly less than every letter in <code>a</code> in the alphabet.</li>
	<li>Both <code>a</code> and <code>b</code> consist of only one distinct letter.</li>
</ul>

Return the minimum number of operations needed to achieve your goal.

&nbsp;
Example 1:

<pre>
Input: a = &quot;aba&quot;, b = &quot;caa&quot;
Output: 2
Explanation: Consider the best way to make each condition true:
1) Change b to &quot;ccc&quot; in 2 operations, then every letter in a is less than every letter in b.
2) Change a to &quot;bbb&quot; and b to &quot;aaa&quot; in 3 operations, then every letter in b is less than every letter in a.
3) Change a to &quot;aaa&quot; and b to &quot;aaa&quot; in 2 operations, then a and b consist of one distinct letter.
The best way was done in 2 operations (either condition 1 or condition 3).
</pre>

Example 2:

<pre>
Input: a = &quot;dabadd&quot;, b = &quot;cda&quot;
Output: 3
Explanation: The best way is to make condition 1 true by changing b to &quot;eee&quot;.
</pre>

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= a.length, b.length &lt;= 105</code></li>
	<li><code>a</code> and <code>b</code> consist only of lowercase letters.</li>
</ul>

第 225 场周赛

weekly-contest-225

minCharacters

Change Minimum Characters to Satisfy One of Three Conditions

Hash Table

String

Counting

Prefix Sum

给你两个字符串 <code>a</code> 和 <code>b</code> ，二者均由小写字母组成。一步操作中，你可以将 <code>a</code> 或 <code>b</code> 中的 任一字符 改变为 任一小写字母 。

操作的最终目标是满足下列三个条件 之一 ：

<ul>
	<li><code>a</code> 中的 每个字母 在字母表中 严格小于 <code>b</code> 中的 每个字母 。</li>
	<li><code>b</code> 中的 每个字母 在字母表中 严格小于 <code>a</code> 中的 每个字母 。</li>
	<li><code>a</code> 和 <code>b</code> 都 由 同一个 字母组成。</li>
</ul>

返回达成目标所需的 最少 操作数。

 

示例 1：

<pre>输入：a = "aba", b = "caa"
输出：2
解释：满足每个条件的最佳方案分别是：
1) 将 b 变为 "ccc"，2 次操作，满足 a 中的每个字母都小于 b 中的每个字母；
2) 将 a 变为 "bbb" 并将 b 变为 "aaa"，3 次操作，满足 b 中的每个字母都小于 a 中的每个字母；
3) 将 a 变为 "aaa" 并将 b 变为 "aaa"，2 次操作，满足 a 和 b 由同一个字母组成。
最佳的方案只需要 2 次操作（满足条件 1 或者条件 3）。
</pre>

示例 2：

<pre>输入：a = "dabadd", b = "cda"
输出：3
解释：满足条件 1 的最佳方案是将 b 变为 "eee" 。
</pre>

 

提示：

<ul>
	<li><code>1 &lt;= a.length, b.length &lt;= 105</code></li>
	<li><code>a</code> 和 <code>b</code> 只由小写字母组成</li>
</ul>