# String Compression

{% hint style="info" %}
String, Iterative approach
{% endhint %}

Implement a method to perform basic string compression using the counts of repeated characters. For example, the string `aabcccccaaa` would become `a2blc5a3`. If the "compressed" string would not become smaller than the original string, your method should return the original string. You can assume the string has only uppercase and lowercase letters (a - z).

### Solutions

#### Approach - Copy characters to new String

At first glance, implementing this method seems fairly straightforward, but perhaps a bit tedious. We iterate through the string, copying characters to a new string and counting the repeats. At each iteration, check if the current character is the same as the next character. If not, add its compressed version to the result.

#### Steps

1. First check if string is null, then return string.
2. Create a new empty string to store the characters.
3. Create character counter variable.
4. Run loop over the length of string and increment character count. Check if current character is not same a next one then, add current character into result string and also check if current string counter value is greater than one, then add counter value also into result string. Now, reset counter to zero.
5. Return new string.

```csharp
    public string Compress(string str)
    {
        if (str is null)
            return str;

        string final = "";

        int count = 0;
        for (int i = 0; i < str.Length; i++)
        {
            count++;
            if (i + 1 >= str.Length || str[i] != str[i + 1])
            {
                final += str[i + 1 >= str.Length ? str.Length - 1 : i];

                if (count > 1)
                    final += count;
                count = 0;

            }

        }

        return final;
    }
```

> Complexity

* **Time Complexity:** O(n + k²)
* **Auxiliary Space:** O(n)

The runtime is O(n + k²), where `n` is the size of the original string and `k` is the number of character sequences. For example, if the string is `aabccdeeaa`, then there are six charactes sequences. It's slow because string concatenation operates in O(n²) time. We can fix this by using a `StringBuilder`.

#### Approach - Copy characters to StringBuilder

***

#### Steps

1. First check if string is null, then return string.
2. Create a new StringBuilder instance to store the characters.
3. Create character counter variable.
4. Run loop over the length of string and increment character count. Check if current character is not same a next one then, add current character into result StringBuilder and also check if current string counter value is greater than one, then add counter value also into result StringBuilder. Now, reset counter to zero.
5. Return new string.

```csharp
public string Compress(string str)
    {
        if (str is null)
            return str;

        StringBuilder sb = new StringBuilder(str.Length / 2);

        int count = 0;
        for (int i = 0; i < str.Length; i++)
        {
            count++;
            if (i + 1 >= str.Length || str[i] != str[i + 1])
            {
                sb.Append(str[i + 1 >= str.Length ? str.Length - 1 : i]);
                if (count > 1)
                    sb.Append(count);
                count = 0;

            }
        }

        return sb.ToString();
    }

```

> Complexity

* **Time Complexity:** O(n)
* **Auxiliary Space:** O(n)


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://docs-57.gitbook.io/data-structure-and-algorithms/problems/string/string-compression.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.