StackStalk
  • Home
  • Java
    • Java Collection
    • Spring Boot Collection
  • Python
    • Python Collection
  • C++
    • C++ Collection
    • Progamming Problems
    • Algorithms
    • Data Structures
    • Design Patterns
  • General
    • Tips and Tricks

Wednesday, July 11, 2012

Compress a string

 July 11, 2012     Programming problems in CPP     No comments   

Write a program to compress a string. If input is "aabbb" expected output is "a2b3"

The approach:-
  1. Have 2 pointers read and write to the input string.
  2. Scan the string using read pointer.
  3. If similar characters are seen keep incrementing a count.
  4. If character sequence changes, write the character and the count value at the write pointer.
  5. Finally terminate the string with a null character.

C++ program to compress a string

#include <iostream>
using namespace std;

int main() 
{ 
	char input[] = "aaabbcccddeeee"; 
	char* read = input; 
	char* write = input; 

	char c = input[0]; 
	int count = 0; 
	while ( *read != '\0' ) {  
		if ( *read == c ) {   
			count++;  
		}  
		else {   
			*write++ = c;   
			*write++ = count + '0';   
			count = 1;  
		}  
		c = *read;  
		read++; 
	} 
	*write++ = c; 
	*write++ = count + '0'; 
	*write = '\0'; 
	cout << input << endl; 
	return 0;
}
Output:-
a3b2c3d2e4

Java program to compress a string

In Java, an additional StringBuilder could be used to store the output since String is immutable. Otherwise the approach to compress is the same.
package com.stackstalk;

public class CompressString {

  public static String compress(String input) {
	  
    StringBuilder output = new StringBuilder();
		
    if ( input.length() == 0 )
        return output.toString();
		
    char c = input.charAt(0);		
    int count = 0;
		
    for ( int index = 0; index < input.length(); index++ ) {
        if ( input.charAt(index) == c ) 
            count++;			
    else {
            output.append(c);
            output.append(count);
            c = input.charAt(index);
            count = 1;
        }
    }
		
    output.append(c);
    output.append(count);
		
    return output.toString();
  }
	
  public static void main(String[] args) {
    System.out.println(compress("a"));
    System.out.println(compress("aaddbbdd"));
    System.out.println(compress("aabbbbccddde"));
  }
}
Output:
a1
a2d2b2d2
a2b4c2d3e1
  • Share This:  
Newer Post Older Post Home

0 comments:

Post a Comment

Follow @StackStalk
Get new posts by email:
Powered by follow.it

Popular Posts

  • Avro Producer and Consumer with Python using Confluent Kafka
    In this article, we will understand Avro a popular data serialization format in streaming data applications and develop a simple Avro Produc...
  • Monitor Spring Boot App with Micrometer and Prometheus
    Modern distributed applications typically have multiple microservices working together. Ability to monitor and manage aspects like health, m...
  • Server-Sent Events with Spring WebFlux
    In this article we will review the concepts of server-sent events and work on an example using WebFlux. Before getting into this article it ...
  • Implement caching in a Spring Boot microservice using Redis
    In this article we will explore how to use Redis as a data cache for a Spring Boot microservice using PostgreSQL as the database. Idea is to...
  • Python FastAPI microservice with Okta and OPA
    Authentication (AuthN) and Authorization (AuthZ) is a common challenge when developing microservices. In this article, we will explore how t...
  • Spring Boot with Okta and OPA
    Authentication (AuthN) and Authorization (AuthZ) is a common challenge when developing microservices. In this article, we will explore how t...
  • Getting started with Kafka in Python
    This article will provide an overview of Kafka and how to get started with Kafka in Python with a simple example. What is Kafka? ...
  • Getting started in GraphQL with Spring Boot
    In this article we will explore basic concepts on GraphQL and look at how to develop a microservice in Spring Boot with GraphQL support. ...

Copyright © StackStalk