string-compression-iii

java

python3

python

javascript

typescript

csharp

golang

kotlin

swift

rust

ruby

dart

scala

elixir

erlang

racket

cangjie

bash

mysql

mssql

postgresql

oraclesql

pythondata

Each time, just cut the same character in prefix up to at max 9 times. It’s always better to cut a bigger prefix.

Algorithms

Given a string <code>word</code>, compress it using the following algorithm:

<ul>
	<li>Begin with an empty string <code>comp</code>. While <code>word</code> is not empty, use the following operation:

	<ul>
		<li>Remove a maximum length prefix of <code>word</code> made of a single character <code>c</code> repeating at most 9 times.</li>
		<li>Append the length of the prefix followed by <code>c</code> to <code>comp</code>.</li>
	</ul>
	</li>
</ul>

Return the string <code>comp</code>.

&nbsp;
Example 1:

<div class="example-block">
Input: word = &quot;abcde&quot;

Output: &quot;1a1b1c1d1e&quot;

Explanation:

Initially, <code>comp = &quot;&quot;</code>. Apply the operation 5 times, choosing <code>&quot;a&quot;</code>, <code>&quot;b&quot;</code>, <code>&quot;c&quot;</code>, <code>&quot;d&quot;</code>, and <code>&quot;e&quot;</code> as the prefix in each operation.

For each prefix, append <code>&quot;1&quot;</code> followed by the character to <code>comp</code>.
</div>

Example 2:

<div class="example-block">
Input: word = &quot;aaaaaaaaaaaaaabb&quot;

Output: &quot;9a5a2b&quot;

Explanation:

Initially, <code>comp = &quot;&quot;</code>. Apply the operation 3 times, choosing <code>&quot;aaaaaaaaa&quot;</code>, <code>&quot;aaaaa&quot;</code>, and <code>&quot;bb&quot;</code> as the prefix in each operation.

<ul>
	<li>For prefix <code>&quot;aaaaaaaaa&quot;</code>, append <code>&quot;9&quot;</code> followed by <code>&quot;a&quot;</code> to <code>comp</code>.</li>
	<li>For prefix <code>&quot;aaaaa&quot;</code>, append <code>&quot;5&quot;</code> followed by <code>&quot;a&quot;</code> to <code>comp</code>.</li>
	<li>For prefix <code>&quot;bb&quot;</code>, append <code>&quot;2&quot;</code> followed by <code>&quot;b&quot;</code> to <code>comp</code>.</li>
</ul>
</div>

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= word.length &lt;= 2 * 105</code></li>
	<li><code>word</code> consists only of lowercase English letters.</li>
</ul>

第 399 场周赛

weekly-contest-399

compressedString

高级工程师

String Compression III

String Compression

string-compression

压缩字符串

String Compression II

string-compression-ii

压缩字符串 II

String

给你一个字符串 <code>word</code>，请你使用以下算法进行压缩：

<ul>
	<li>从空字符串 <code>comp</code> 开始。当 <code>word</code> 不为空 时，执行以下操作：

	<ul>
		<li>移除 <code>word</code> 的最长单字符前缀，该前缀由单一字符 <code>c</code> 重复多次组成，且该前缀长度 最多 为 9 。</li>
		<li>将前缀的长度和字符 <code>c</code> 追加到 <code>comp</code> 。</li>
	</ul>
	</li>
</ul>

返回字符串 <code>comp</code> 。

&nbsp;

&nbsp;

示例 1：

<div class="example-block">
输入：word = "abcde"

输出："1a1b1c1d1e"

解释：

初始时，<code>comp = ""</code> 。进行 5 次操作，每次操作分别选择 <code>"a"</code>、<code>"b"</code>、<code>"c"</code>、<code>"d"</code> 和 <code>"e"</code> 作为前缀。

对每个前缀，将 <code>"1"</code> 和对应的字符追加到 <code>comp</code>。
</div>

示例 2：

<div class="example-block">
输入：word = "aaaaaaaaaaaaaabb"

输出："9a5a2b"

解释：

初始时，<code>comp = ""</code>。进行 3 次操作，每次操作分别选择 <code>"aaaaaaaaa"</code>、<code>"aaaaa"</code> 和 <code>"bb"</code> 作为前缀。

<ul>
	<li>对于前缀 <code>"aaaaaaaaa"</code>，将 <code>"9"</code> 和 <code>"a"</code> 追加到 <code>comp</code>。</li>
	<li>对于前缀 <code>"aaaaa"</code>，将 <code>"5"</code> 和 <code>"a"</code> 追加到 <code>comp</code>。</li>
	<li>对于前缀 <code>"bb"</code>，将 <code>"2"</code> 和 <code>"b"</code> 追加到 <code>comp</code>。</li>
</ul>
</div>

&nbsp;

提示：

<ul>
	<li><code>1 &lt;= word.length &lt;= 2 * 105</code></li>
	<li><code>word</code> 仅由小写英文字母组成。</li>
</ul>

压缩字符串 III

执行通过

错误解答

超出内存限制

超出输出限制

超出时间限制

执行出错

内部出错

编译出错

超时

Restrictions Failed

给你一个字符串 word，请你使用以下算法进行压缩：

 * 从空字符串 comp 开始。当 word 不为空 时，执行以下操作：
 * 移除 word 的最长单字符前缀，该前缀由单一字符 c 重复多次组成，且该前缀长度 最多 为 9 。
 * 将前缀的长度和字符 c 追加到 comp 。

返回字符串 comp 。

 

 

示例 1：

输入：word = "abcde"

输出："1a1b1c1d1e"

解释：

初始时，comp = "" 。进行 5 次操作，每次操作分别选择 "a"、"b"、"c"、"d" 和 "e" 作为前缀。

对每个前缀，将 "1" 和对应的字符追加到 comp。

示例 2：

输入：word = "aaaaaaaaaaaaaabb"

输出："9a5a2b"

解释：

初始时，comp = ""。进行 3 次操作，每次操作分别选择 "aaaaaaaaa"、"aaaaa" 和 "bb" 作为前缀。

 * 对于前缀 "aaaaaaaaa"，将 "9" 和 "a" 追加到 comp。
 * 对于前缀 "aaaaa"，将 "5" 和 "a" 追加到 comp。
 * 对于前缀 "bb"，将 "2" 和 "b" 追加到 comp。

 

提示：

 * 1 <= word.length <= 2 * 105
 * word 仅由小写英文字母组成。