2024-11-04 Daily Challenge

Posted on:
Posted modified:
In: DailyChallenge

Today I have done leetcode's November LeetCoding Challenge with cpp.

November LeetCoding Challenge 4

Description

String Compression III

Given a string word, compress it using the following algorithm:

  • Begin with an empty string comp. While word is not empty, use the following operation: 
    <ul>
	<li>Remove a maximum length prefix of <code>word</code> made of a <em>single character</em> <code>c</code> repeating <strong>at most</strong> 9 times.</li>
	<li>Append the length of the prefix followed by <code>c</code> to <code>comp</code>.</li>
</ul>
</li>

Return the string comp.

 

Example 1:

Input: word = "abcde"

Output: "1a1b1c1d1e"

Explanation:

Initially, comp = "". Apply the operation 5 times, choosing "a", "b", "c", "d", and "e" as the prefix in each operation.

For each prefix, append "1" followed by the character to comp.

Example 2:

Input: word = "aaaaaaaaaaaaaabb"

Output: "9a5a2b"

Explanation:

Initially, comp = "". Apply the operation 3 times, choosing "aaaaaaaaa", "aaaaa", and "bb" as the prefix in each operation.

  • For prefix "aaaaaaaaa", append "9" followed by "a" to comp.
  • For prefix "aaaaa", append "5" followed by "a" to comp.
  • For prefix "bb", append "2" followed by "b" to comp.

 

Constraints:

  • 1 <= word.length <= 2 * 105
  • word consists only of lowercase English letters.

Solution

class Solution {
public:
  string compressedString(string word) {
    string answer;
    char cur = word.front();
    int count = 0;
    for(auto c : word) {
      if(count == 9 || cur != c) {
        answer.push_back(count + '0');
        answer.push_back(cur);
        count = 0;
        cur = c;
      }
      if(cur == c) {
        count += 1;
      }
    }
    answer.push_back(count + '0');
    answer.push_back(cur);
    return answer;
  }
};
Algorithm