In the **String Compression** problem, we have given an array a[ ] of type char. Compress it as the character and count of a particular character (if the count of character is 1 then the only character is stored in a compressed array). The length of the compressed array should be equal to less than the original array. Return the length of the compressed array.

Table of Contents

## Example

**Input : **a[ ] = {‘a’, ‘a’, ‘a’, ‘b’, ‘b’}

**Output :** 4 (as the compressed array will be {‘a’, ‘3’, ‘b’, ‘2’})

**Input : **a[ ] = {‘a’}

**Output :** 1 (as the compressed array will be {‘a’}. As count = 1 so compressed array will only contain the character and not the count)

## Algorithm for String Compression

- Initialize a character array of size n.
- Declare a variable result as 0 and count as 1.
- Traverse through the array and count the characters of a similar kind.
- If the count of a character is 1 increment the result by 1 as the only character is supposed to be in the compressed array.
- Else increment the result by 2 for both character and its count.
- Print the result.

**Time Complexity: **O(n) where n is the number of elements in the array. As we are traversing every element once therefore time complexity is O(n).

**Auxiliary Space: **O(1) because we don’t use any auxiliary space to perform the operations.

### C++ Program for String Compression

#include <bits/stdc++.h> using namespace std; void compression(char a[], int n){ int result = 0; for(int i=0; i<n; i++){ int count = 1; while(i<n-1 && a[i] == a[i + 1]){ count++; i++; } if(count==1){ result++; } else{ result = result + 2; } } cout<<result; } int main(){ char a[] = {'a', 'a', 'a', 'b', 'b'}; int n = sizeof(a)/sizeof(a[0]); compression(a, n); return 0; }

4

### Java Program for String Compression

class StringCompression{ static void compression(char[] a, int n){ int result = 0; for(int i=0; i<n; i++){ int count = 1; while(i<n-1 && a[i] == a[i+1]){ count++; i++; } if(count==1){ result++; } else{ result = result + 2; } } System.out.println(result); } public static void main(String[] args){ char[] a = {'a', 'a', 'a', 'b', 'b'}; int n = a.length; compression(a, n); } }

4