String Compression - TutorialCup

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; 
}

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); 
    } 
}

References