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.....:)
This comment has been removed by the author.
ReplyDeletecan any explain the logic pls...
Delete#include
Delete#include
int main(){
char str[1000];
gets(str);
int len=strlen(str);
int i,j,count=1;
for(i=0;ii&&str[j]!='\0';j--)
{
if(str[i]==str[j])
{
count++;
if(str[j+1]=='\0')
{
printf("%c%d ",str[i],count);
}
}
else
{
printf("%c%d ",str[i],count);
count=1;
if(str[j+1]=='\0')
{
printf("%c%d ",str[i+1],count);
}
}
}
}
}
This comment has been removed by the author.
ReplyDelete#include
ReplyDelete#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;
}
Doesn't compress the string 'inplace'
Deletedude y u have used the 48+c+1.. i could nt understand.?
Deletewhat if the count >=10;will your logic of 48+c+1 will work in that case?
DeleteHi ,
ReplyDeleteYour Program not working for input like aaabbbaaaccc : a3b3a3c3 which is wrong
This comment has been removed by the author.
ReplyDeleteAll the corner case scenarios are taken care by this function
ReplyDeletevoid 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';
}
Here is the code to this inplace..that too in O(n) time .
ReplyDelete#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;
}
if i take iput as abc it generate a1b1c1. so is that taking less space as input string.
ReplyDelete#include
ReplyDelete#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();
}
String s = "aaaaaabbbdcdcccccccc";
ReplyDeletechar[] 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);
namespace a2b3c4
ReplyDelete{
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();
}
}
}
public class StringCompressDemo {
ReplyDeletepublic 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);
}
}
}
str= "abaaaabbbbm555bbbccvvvvvvccccc"
ReplyDeleteflag = 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
package com.shashi.thread;
ReplyDeleteimport 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();
}
}
thanks alot bro
Delete
ReplyDeleteRun 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;
}
void StringPattern(char* str)
ReplyDelete{
size_t len = strlen(str);
char* out = new char[len + 1];
memset(out, 0, len + 1);
int ncount = 1;
for (size_t i = 0, j = 0; i < len; i++)
{
if (str[i] == str[i + 1])
{
ncount++;
}
else
{
out[j++] = str[i];
out[j++] = 48 + ncount;
ncount = 1;
}
}
std::cout << out << std::endl;
}
class StrOut
ReplyDelete{
public static void main(String args[])
{
String s="aabbbccc";
int count=1;
String t="";
for(int i=0;i<s.length()-1;i++)
{
if(s.charAt(i)==s.charAt(i+1))
{
count++;
t=t+s.charAt(i);
}
else
{
System.out.println(t+" "+count);
count=1;
}
}
int n=s.length()-1;
System.out.println(s.charAt(n)+""+count);
}
}
Follow the program any string to compress in c language
ReplyDelete100% correct program
any error plz reply fast
//i m joker
#include
# define MAX 100
int main()
{
char str[MAX];
printf("Enter a string to compress :");
gets(str);
char current = str[0];
int count = 1;
for(int i = 1; str[i]!='\0'; i++)
if(str[i] == current)
count++;
else
{
printf("%c%d",current,count);
current = str[i];
count = 1;
}
printf("%c%d",current,count);
return 0;
}
initially 1 is printed
DeleteMy java version
ReplyDeletepublic static void main(String[] args) {
char[] str = "aaabbbcc".toCharArray();
StringBuilder strcompress = compressString(str);
System.out.println(strcompress.toString());
}
private static StringBuilder compressString(char[] str)
{
StringBuilder strcompress = new StringBuilder();
int counter = 1;
if (str.length == 1)
strcompress.append(str[0]);
for (int i = 0; i < str.length - 1; i++) {
if (str[i] == str[i + 1]) {
counter++;
//check if it's the last position
if (i + 1 == str.length - 1) {
strcompress.append(str[i] + "" + counter);
}
} else {
if (counter == 1) {
strcompress.append(str[i]);
} else {
strcompress.append(str[i] + "" + counter);
}
counter = 1;
//check if it's the last position
if (i + 1 == str.length - 1) {
strcompress.append(str[i + 1]);
}
}
}
return strcompress;
}