This is called Run-Length-Encoding (RLE) of a string.
Its purpose is to save space.So in case of abcdef,I think the output needed
is abcdef (1 is implicit).
The added benefit is it makes the solution in-place.
Approach:- (In-place and Linear Time)
Start from the left of string and PREVIOUS_CHAR = str[0]
move forward till u match the CURRENT_CHAR with PREVIOUS_CHAR and keep
count of PREVIOUS_CHAR
At any point if (PREVIOUS_CHAR!=CURRENT_CHAR)
put the count of prev_char next to the start position of the previous
character.
Below is the working code :-
void torle(char *str)
{ int i=0,j=0,k=0,cnt=1;
char cur_char=str[0],num[100];
while(str[j+1])
{
cnt=1;
while(str[j+1]==cur_char && str[j]!='\0'){
j++;
cnt++;
}
str[i++]=cur_char;
if( cnt>9 ){
itoa(cnt,num);
k=0;
while(num[k]) str[i++]=num[k++];
}
else if( cnt>1 && cnt<10 )
str[i++]= cnt+'0';
j++;
if(str[j]) cur_char=str[j];
}
if(i!=0){
if(cnt==1)
str[i++]=cur_char;
str[i]='\0';
}
}
On Saturday, 26 May 2012 04:32:35 UTC+5:30, utsav sharma wrote:
>
> Implement a method to perform basic string compression using the counts of
> repeated characters.(inplace)
>
> eg:- input: "aaabbbbbcdef"
> output:"3a5b1c1d1e1f".
>
> what should be my approach to this problem
>
> if i calculate the size of array required to store the output string
> and start from the last of the array then i wldn't get the right answer of
> above input case.
>
> and if start from front then i wldn't get the right answer of this input
> case
> eg:- input: "abcdef"
> output: "1a1b1c1d1e1f"
>
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To view this discussion on the web visit
https://groups.google.com/d/msg/algogeeks/-/4LxWHEUJuK8J.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
