# One of the Best Algorithms Related to String Manipulation

Page 1 of 1

## 1 Replies - 916 Views - Last Post: 06 March 2013 - 06:10 PMRate Topic: //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'http://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=314545&amp;s=ae450f95ae16ca4de6103391376d8031&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

### #1 burakaltr

• D.I.C Regular

Reputation: 91
• Posts: 274
• Joined: 07-November 10

# One of the Best Algorithms Related to String Manipulation

Posted 06 March 2013 - 05:33 PM

One of the Hardest Thinking is involved in this Problem below, I think.

What Do You Think ?

Thanks !

Quote

Run-length encoding (RLE) is a simple "compression algorithm" (an algorithm which takes a block of data and reduces its size, producing a block that contains the same information in less space). It works by replacing repetitive sequences of identical data items with short "tokens" that represent entire sequences. Applying RLE to a string involves finding sequences in the string where the same character repeats. Each such sequence should be replaced by a "token" consisting of:

the number of characters in the sequence
the repeating character
If a character does not repeat, it should be left alone.

For example, consider the following string:

qwwwwwwwwweeeeerrtyyyyyqqqqwEErTTT
After applying the RLE algorithm, this string is converted into:

q9w5e2rt5y4qw2Er3T
In the compressed string, "9w" represents a sequence of 9 consecutive lowercase "w" characters. "5e" represents 5 consecutive lowercase "e" characters, etc.

Write a program that takes a string as input, compresses it using RLE, and outputs the compressed string. Case matters - uppercase and lowercase characters should be considered distinct. You may assume that there are no digit characters in the input string. There are no other restrictions on the input - it may contain spaces or punctuation. There is no need to treat non-letter characters any differently from letters.

Is This A Good Question/Topic? 0

## Replies To: One of the Best Algorithms Related to String Manipulation

### #2 cfoley

• Cabbage

Reputation: 1905
• Posts: 3,949
• Joined: 11-December 07

## Re: One of the Best Algorithms Related to String Manipulation

Posted 06 March 2013 - 06:10 PM

If you are finding it tricky then try these instead of trying to jump straight to the answer:

1. Loop through the characters of the string and print out the character count so far. This should just give you the numbers 1 to the length of the string.

2. Now reset the counter any time the character you are looking at is not the same as the previous one.

3. Now only display the numbers immediately before you reset the counter. Don't display the intermediate results. Be careful to include the first and last numbers!

4. Display the character after the number.

5. Add a condition to avoid displaying 1s.
Was This Post Helpful? 1

Page 1 of 1

 .related ul { list-style-type: circle; font-size: 12px; font-weight: bold; } .related li { margin-bottom: 5px; background-position: left 7px !important; margin-left: -35px; } .related h2 { font-size: 18px; font-weight: bold; } .related a { color: blue; }