Tuesday, 5 June 2012

Compress a string aaabbbcc into a3b3c2 : O(n) C code


Amazon Interview: String Compression



Problem Statement

Given a string "aaabbbcc", compress it, = "a3b3c2" . Given that output string's length is always smaller than input string, you have do it inplace. No extra space like array should be used.


Solution

#include<stdio.h>
#include<string.h>

void compress(char *str,int len, int act);
char str[100];
int length;

int main()
{
scanf("%s",str);
length=strlen(str);
//compression
//we need a recursive sol so that
//cases like abbbccc or abcccc are also taken care of
compress(str,0,0);
printf("%s",str);
scanf("%d",&length);

}

//recursive code - prefered
void compress(char *str,int len, int act) {

if(len<length) {
    int k=len;
    int count=0;
    int c, n;
    while(str[k]==str[len]){
        len++; count++;
    }
    n = 0;
    c=count;
    do {
        c /= 10;
        n++;
    } while (c != 0);
   
    compress(str,len,act+n+1);
   
    str[act]=str[k];
    if(k+count==length)
       str[act+n+1]='\0';
    for(c=0;c<n;c++) {
        str[act+n-c]=(count%10)+48;
        count=count/10;
    }

}
return;
}


Time Complexity:  O(n)


If you found this blog somewhat helpful, please share it and Keep Visiting.....:)

20 comments:

  1. This comment has been removed by the author.

    ReplyDelete
  2. This comment has been removed by the author.

    ReplyDelete
  3. #include
    #include
    int main()
    {
    int i=0,c=0,j=0;
    char str[20],out[40];
    printf("enter a string ");
    gets(str);
    puts(str);
    while(str[i]!=NULL)
    {
    c=0;
    out[j]=str[i]; put new char in another string
    while(str[i]==str[i+1])
    //run loop till char are same
    {
    c++; i++; //increase count
    }
    i++;
    j++;
    out[j]=48+c+1; // put count in another string
    j++;
    }
    out[j]=NULL;
    printf("%s\n",out);
    return 0;
    }

    ReplyDelete
    Replies
    1. Doesn't compress the string 'inplace'

      Delete
    2. dude y u have used the 48+c+1.. i could nt understand.?

      Delete
    3. what if the count >=10;will your logic of 48+c+1 will work in that case?

      Delete
  4. Hi ,

    Your Program not working for input like aaabbbaaaccc : a3b3a3c3 which is wrong

    ReplyDelete
  5. This comment has been removed by the author.

    ReplyDelete
  6. All the corner case scenarios are taken care by this function
    void compress(char * str)
    {
    int i,count=1,insert_index=1;
    char temp=str[0],buffer[2];
    for(i=1;i=1)
    str[insert_index++]=*itoa(count,buffer,10);
    str[insert_index]='\0';
    }

    ReplyDelete
  7. Here is the code to this inplace..that too in O(n) time .

    #include
    #include
    using namespace std;

    int doWork(char* str,int index,int &countValue)
    {
    if(str[index]=='\0')
    {
    countValue=0;
    return -1;
    }
    else{
    int j=index+1;
    countValue = 1;
    while(str[j]==str[index])
    {

    j++;countValue++;
    }
    if(str[j]=='\0')
    return -1;
    else
    return j;
    }
    }
    int main()
    {
    char str[50];
    cout<<"Enter the string";
    cin>>str;
    int index=0;
    int countValue=0;
    int writingIndex=0;
    int from = doWork(&str[0],index,countValue);
    while(from != -1)
    {
    str[writingIndex++]=str[index];
    str[writingIndex++]=(countValue)+'0';
    index=from;
    from=doWork(&str[0],index,countValue);
    }
    if(countValue)
    {
    str[writingIndex++]=str[index];
    str[writingIndex++]=(countValue)+ '0';
    str[writingIndex]='\0';
    }
    cout<<str;

    }

    ReplyDelete
  8. if i take iput as abc it generate a1b1c1. so is that taking less space as input string.

    ReplyDelete
  9. #include
    #include
    int main()
    {
    char str[15];
    int i,c1,n;
    printf("Enter the string:");
    scanf("%s",&str);
    n=strlen(str);
    for(i=0;i<n;i++)
    {
    c1=0;
    printf("%c",str[i]);
    while(str[i]==str[i+1])
    {
    c1++;
    i++;
    }
    printf("%d",c1+1);
    }
    getch();
    }

    ReplyDelete
  10. String s = "aaaaaabbbdcdcccccccc";
    char[] c = s.toCharArray();
    s="";
    int j=1;
    for(int i = 0; i < c.length; i++) {
    if(i == c.length-1) s= s+c[i]+j;
    else {
    if(c[i] == c[i+1]) {
    j++;
    } else {
    s= s+c[i]+j;
    j=1;
    }
    }
    }
    System.out.println(s);

    ReplyDelete
  11. namespace a2b3c4
    {
    class Program
    {
    static void Main(string[] args)
    {
    string str = "aaaaaaaaaaabbbcccd";
    char[] strc = str.ToCharArray();

    int writeIndex=0;
    int readIndex=0;
    int count;

    for (readIndex = 0; readIndex < strc.Length; )
    {
    count = 0;
    while (readIndex < strc.Length && strc[writeIndex] == strc[readIndex])
    {
    readIndex++;
    count++;
    }
    writeIndex++;
    if (count > 1)
    {
    do
    {
    strc[writeIndex] = (char)(count % 10 + '0');
    count /= 10;
    writeIndex++;
    } while (count != 0);
    }
    if (readIndex < strc.Length)
    {
    strc[writeIndex] = strc[readIndex];
    }
    else
    {
    strc[writeIndex] = '\0';
    }
    }

    Console.WriteLine(new string (strc,0,writeIndex));
    Console.ReadLine();

    }
    }
    }

    ReplyDelete
  12. public class StringCompressDemo {

    public static void main(String[] args) {
    compress("mmmmmmmmmmmddddHHmmmdddyffff");
    compress("kkk");
    }

    public static void compress(String str) {
    String res = "";
    if (str != null && !str.isEmpty()) {
    int count = 0;
    char currChar = 0, prevChar = 0;
    for (int i = 0; i < str.length(); i++) {
    if (i == 0) {
    currChar = prevChar = str.charAt(i);
    }
    currChar = str.charAt(i);
    if (currChar != prevChar) {
    res = res + prevChar + count;
    count = 1;
    } else {
    count++;
    }
    prevChar = currChar;
    }
    res = res + prevChar + count;
    System.out.println("Compression Result:" + res);
    }
    }
    }

    ReplyDelete
  13. str= "abaaaabbbbm555bbbccvvvvvvccccc"
    flag = 1
    Dim cstr
    cstr=Mid(str,1,1)&"1"

    For i=1 to len(str)

    If Mid(str,i,1)=Mid(str,i+1,1) Then


    Flag=Flag+1
    cstr = Mid(cstr,1,Len(cstr)-1) & Flag

    Else
    If i<>len(str) Then
    cstr = cstr & Mid(str,i+1,1) & 1
    End if
    Flag = 1

    End If

    Next

    msgbox cstr

    ReplyDelete
  14. package com.shashi.thread;

    import java.util.Scanner;

    public class WordCount
    {
    public static void main(String args[])
    {
    Scanner sc = new Scanner(System.in);
    int count = 0;
    String st = sc.nextLine();
    char ch = st.charAt(0);

    StringBuffer sb = new StringBuffer();
    for (int i = 0; i < st.length(); i++)
    {

    if (ch == st.charAt(i))
    {

    count++;
    }
    else
    {
    sb.append(ch + "" + count);
    count = 1;
    ch = st.charAt(i);
    }

    }
    sb.append(ch + "" + count);
    System.out.print(sb);
    sc.close();

    }
    }

    ReplyDelete

  15. Run it in c++ 14 compiler

    #include

    using namespace std;

    int main()
    {
    int alpha[26]={0},i=0;
    string q,a="";
    cin>>q;
    for(int i=0;i<q.length();i++)
    {
    ++alpha[(q[i]-'a')];
    }
    for(int i=0;i<26;i++)
    {
    if(alpha[i]!=0)
    {
    a=a+char(i+'a')+to_string(alpha[i]);
    }
    }


    cout<<a;
    return 0;
    }

    ReplyDelete