# String Compression

Difficulty Level Medium
Frequently asked in Amazon Apple Citrix Expedia Facebook Goldman Sachs IBM Microsoft Yandex
StringViews 3466

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. ## 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

1. Initialize a character array of size n.
2. Declare a variable result as 0 and count as 1.
3. Traverse through the array and count the characters of a similar kind.
4. 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.
5. Else increment the result by 2 for both character and its count.
6. 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);

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`

References

Translate »