maximum-score-from-removing-substrings

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 a string <code>s</code> and two integers <code>x</code> and <code>y</code>. You can perform two types of operations any number of times.

<ul>
	<li>Remove substring <code>&quot;ab&quot;</code> and gain <code>x</code> points.

	<ul>
		<li>For example, when removing <code>&quot;ab&quot;</code> from <code>&quot;cabxbae&quot;</code> it becomes <code>&quot;cxbae&quot;</code>.</li>
	</ul>
	</li>
	<li>Remove substring <code>&quot;ba&quot;</code> and gain <code>y</code> points.
	<ul>
		<li>For example, when removing <code>&quot;ba&quot;</code> from <code>&quot;cabxbae&quot;</code> it becomes <code>&quot;cabxe&quot;</code>.</li>
	</ul>
	</li>
</ul>

Return the maximum points you can gain after applying the above operations on <code>s</code>.

&nbsp;
Example 1:

<pre>
Input: s = &quot;cdbcbbaaabab&quot;, x = 4, y = 5
Output: 19
Explanation:
- Remove the &quot;ba&quot; underlined in &quot;cdbcbbaaabab&quot;. Now, s = &quot;cdbcbbaaab&quot; and 5 points are added to the score.
- Remove the &quot;ab&quot; underlined in &quot;cdbcbbaaab&quot;. Now, s = &quot;cdbcbbaa&quot; and 4 points are added to the score.
- Remove the &quot;ba&quot; underlined in &quot;cdbcbbaa&quot;. Now, s = &quot;cdbcba&quot; and 5 points are added to the score.
- Remove the &quot;ba&quot; underlined in &quot;cdbcba&quot;. Now, s = &quot;cdbc&quot; and 5 points are added to the score.
Total score = 5 + 4 + 5 + 5 = 19.</pre>

Example 2:

<pre>
Input: s = &quot;aabbaaxybbaabb&quot;, x = 5, y = 4
Output: 20
</pre>

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= s.length &lt;= 105</code></li>
	<li><code>1 &lt;= x, y &lt;= 104</code></li>
	<li><code>s</code> consists of lowercase English letters.</li>
</ul>

maximumGain

Maximum Score From Removing Substrings

Count Words Obtained After Adding a Letter

count-words-obtained-after-adding-a-letter

统计追加字母可以获得的单词数

Stack

Greedy

String

给你一个字符串 <code>s</code> 和两个整数 <code>x</code> 和 <code>y</code> 。你可以执行下面两种操作任意次。

<ul>
	<li>删除子字符串 <code>"ab"</code> 并得到 <code>x</code> 分。

	<ul>
		<li>比方说，从 <code>"cabxbae"</code> 删除 <code>ab</code> ，得到 <code>"cxbae"</code> 。</li>
	</ul>
	</li>
	<li>删除子字符串<code>"ba"</code> 并得到 <code>y</code> 分。
	<ul>
		<li>比方说，从 <code>"cabxbae"</code> 删除 <code>ba</code> ，得到 <code>"cabxe"</code> 。</li>
	</ul>
	</li>
</ul>

请返回对 <code>s</code> 字符串执行上面操作若干次能得到的最大得分。

 

示例 1：

<pre>输入：s = "cdbcbbaaabab", x = 4, y = 5
输出：19
解释：
- 删除 "cdbcbbaaabab" 中加粗的 "ba" ，得到 s = "cdbcbbaaab" ，加 5 分。
- 删除 "cdbcbbaaab" 中加粗的 "ab" ，得到 s = "cdbcbbaa" ，加 4 分。
- 删除 "cdbcbbaa" 中加粗的 "ba" ，得到 s = "cdbcba" ，加 5 分。
- 删除 "cdbcba" 中加粗的 "ba" ，得到 s = "cdbc" ，加 5 分。
总得分为 5 + 4 + 5 + 5 = 19 。</pre>

示例 2：

<pre>输入：s = "aabbaaxybbaabb", x = 5, y = 4
输出：20
</pre>

 

提示：

<ul>
	<li><code>1 &lt;= s.length &lt;= 105</code></li>
	<li><code>1 &lt;= x, y &lt;= 104</code></li>
	<li><code>s</code> 只包含小写英文字母。</li>
</ul>