Coding Challenge Day-4: Problem 1: Perform basic string compression using counts of repeated characters

Hello! So I’m doing a 30 day coding challenge where I solve around 3-5 questions per day and thought of posting them here on my blog so that you guys can join the challenge too!

Welcome to Coding challenge Day 4: Problem 1! Be sure to post your answers, queries etc in the comments!!

Problem: Implement a method to perform basic string compression using counts of repeated characters. For example, the string aabcccccaaa would become a2b1c5a3. 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 upper and lower case letters (a-z)

Sample input: aabcccccaaa
Output: Compressed string: a2b1c5a3

Sample input: book
Output: Compressed string: book

Sample input: ssssaaaaapppppp
Output: Compressed string: s4a5p6

Solution:

• So start by finding the length of the original string and initialise a new string into which you will store the compressed string
• convert the original string into a character array and initialize a variable ‘a’ with the element at the 0 index and also initialize a variable count which will store the count of differnet elements
• start a loop that runs the entire length of character array
• if ‘a’ is equal to the element at thr current index then increase count by one else add ‘a’ to the new_string and also ‘count’, then re-initialize ‘a’ with the new element and ‘count’ to 1.
• once out of the loop don’t forget to add the last count to ‘new
  _string’
• if length of new_string is greater than the orginal string then return the original string else return the ‘new_string’

package string;

public class Program003compress_string {
	
	public static String replace (String str){
		int length = str.length();
		String new_string="";
		char [] sc= str.toCharArray();
		char a= sc[0];
		int count=0;
		
		for(int i=0; i<length; i++ ){
		    if(sc[i]==a){
		    	count++;
		    }
		    else if(sc[i]!=a){
		    	new_string+= a;
		    	new_string+=count;
		    	a= sc[i];
		    	count=1;
		    }
		}
		
		if (count>0){
			new_string+= a;
			new_string+= count;
		}
		
		if(str.length()<new_string.length())
			return str;
		
		
		return new_string;
	}
	
	public static void main (String [] args){
		String str= "ssssaaaaapppppp";
		System.out.println("Compressed string: "+ replace(str));
	}

}

Download Code

References:
1) Cracking the coding interview (by Gayle Laakmann McDowell)

Happy learning!!