Arrays-String interview question 6

Cracking the coding interview

Arrays and String solutions

Hey guys i am providing the solutions for the question given in the Chapter one Arrays and String of the very famous book Cracking the coding interview. All these solutions are written by myself and checked for all the possible cases. Please take a look at them and help your self to solve your problems. If you have any query regarding the solutions or you want to ask something leave your comment and i will get back to you as soon as possible. Happy coding.

Question 6

String Compression: Implement a method to perform basic string compression using the 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 uppercase and lowercase letters (a - z).

Solution
You can find the solution for this problem here.
Solution 1 using java.
This problem is very unique and rarely asked in the interview question but it is always good to learn as much as you can and to prepare for the worst to achieve good things.In this problem you have to remove the repeating characters from the and string and place the number which is equal to the occurrence of that character which in turn reduces the length of the string with keep all the information about the string such as no of times character appearing in the string. But in this process a unique case might occur were the length of the compressed string is larger then the actual string in that case we have to give original strong not the compressed string because our aim is to reduce the length of the string let us understand with an example suppose if a given string is abcdefgh then the compressed sting of this string will be a1b1c1d1e1f1g1h1 as we can see that the length of the compressed string is more then the original string so we have to take care of this case also and write a program that handles this case also.

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
 public static void main (String[] args) throws java.lang.Exception
 {
  // your code goes here
  System.out.println(compress());
 }
 public static String compress()
 {
       String a="aaaaaaaabbbbbbbccccccccccccccccccddddddddddddddeeeeeeeeee";
         int ctr=0;
  StringBuilder b = new StringBuilder(a.length());
  for(int i=0;i=a.length()||a.charAt(i)!=a.charAt(i+1))
   {
    b.append(a.charAt(i));
    b.append(String.valueOf(ctr));
    ctr=0;
   }   
  }
  return b.length()>a.length()?a:b.toString();
 }
}

Note that this approach is not only specific to this type of question you can use this sorting technique in various questions such as if you want to check whether to word are anagrams of one another or not. You can simply sort them and compare them to find out. This approach is also helpful in other questions so i suggest that its better to learn this tricks and keep in mind while attempting the question you may find it useful. You can always search for more coding problems like this to get comfortable to this to approach or you can find new problems where this approach is applicable. So go and search more problems like this and check whether this approach is useful or not and you can tell me about it by commenting and writing about this to me.

Try more and more problems that you find on string and arrays and try to develop an approach the will help you understand problems rather then learning the solution. Once you know how to approach the problem you will able to solve any problem related to strings and array. I wish best of luck to you for your future.