StringBuilder III

Another example where string concatenation leads to TLE while the StringBuilder approach gets to the expected solution. A lot of concatenations using Strings in C# will lead to many objects being created all the time, which not only wastes memory but also time in the process (including GC). This article from SO discusses this theme well: c# - benefits of using a stringbuilder - Stack Overflow

Code is down below, cheers, ACC

String Compression III - LeetCode

3163. String Compression III

Medium

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:
  • Remove a maximum length prefix of word made of a single character c repeating at most 9 times.
  • Append the length of the prefix followed by c to comp.

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.

public string CompressedString(string word)
{
    if (String.IsNullOrEmpty(word)) return word;

    char prev = word[0];
    int count = 1;
    int MAX = 9;

    StringBuilder retVal = new StringBuilder();
    for (int i = 1; i < word.Length; i++)
    {
        if (word[i] != prev || count >= MAX)
        {
            retVal.Append((char)(count + (int)'0'));
            retVal.Append(prev);
            count = 0;
        }
        prev = word[i];
        count++;
    }
    retVal.Append((char)(count + (int)'0'));
    retVal.Append(prev);

    return retVal.ToString();
}