RLE - Run length encoding

no tags 

Ram had to send large amount of data to his friend Vishnu. Since he was concerned about the time and the amount of data transfer it will take, he wanted to compress the data before he sent it. So he turns to you for help.

You need to perform run length encoding on a given string. The encoding is as follows : 'consecutive character count' followed by '!' followed by the 'character'. Do not encode the characters unless they lead to compression !

Input

Input consists of multiple lines of strings s, one string per line, with |s| <= 100000 (read the input till EOF)

Output

For each input string, output a single line printing the run length encoding of the input string

Example

Input:
aabbbbbccccc
aaaabbbbbbbbbbbbbbbccccc Output: aa5!b5!c
4!a15!b5!c

hide comments
Piyush Kumar: 2016-06-10 05:16:27

Does the string also contain spaces?

KD : 2016-05-27 19:42:27

good question AC after 2 WA

suvro_datta: 2016-05-13 15:23:22

scanf("%s",str) == wa
cin>>str == ac
???

Anand: 2016-01-28 13:04:07

O(n) logic in Java gives TLE
Same logic in c gets ac in 0.00

*EDIT*
Gets accepted with some I/O optimization in java also :)

Last edit: 2016-01-28 13:12:34
Arun Vinud: 2015-07-21 06:53:55

@Karan It works.

Last edit: 2015-07-21 06:54:45
Karan: 2015-07-13 22:50:50

its giving wrong answer for java while the program is correct just because of the read from the file i am using while((s=br.readLine())!=null) but its not taking it correct , anybody can suggest me something

Last edit: 2015-07-13 23:00:25
rahul goyal: 2014-12-29 21:29:44

nyc question (y)


Added by:Pandian
Date:2013-12-14
Time limit:1s-2s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:Own