Tech Qu: Write a function to do RLE (Run Length Encoding)

• Given a string, compress using run-length encoding. Example:
  Input: aaabbac
  Output: a3b2ac

First Pass – simplistic solution

Code Snippet

1. /// <summary>
2.  /// Assuming no digits in string.
3.  /// </summary>
4.  /// <param name="s"></param>
5.  /// <returns></returns>
6.  public static string RLEEncode1(string s)
7.  {
8.    var sb = new StringBuilder();
9.    int count = 1;
10.    char current = s[0];
11.    for (int i = 1; i < s.Length; i++)
12.    {
13.      if (current == s[i])
14.      {
15.        count++;
16.      }
17.      else
18.      {
19.        if (count > 1)
20.          sb.AppendFormat("{1}{0}", count, current);
21.        else
22.          sb.Append(current);
23.        count = 1;
24.        current = s[i];
25.      }
26.    }
27.    if (count > 1)
28.      sb.AppendFormat("{1}{0}", count, current);
29.    else
30.      sb.Append(current);  
31.    return sb.ToString();
32.  }

A better solution is to assume that there are no characters > 127 in the string and using the range 128-255 as counter indicators. This solution is shown below.

 

Code Snippet

1. public static string RLEEncode2(string s)
2.     {
3.       var sb = new StringBuilder();
4.       int count = 1;
5.       char current = s[0];
6.       for (int i = 1; i < s.Length; i++)
7.       {
8.         if (current == s[i])
9.         {
10.           count++;
11.           if(count > 127)
12.           {
13.               
14.               sb.Append(current);
15.               sb.Append((char)(count + 127));
16.               count = 1;
17.           }          
18.         }
19.         else
20.         {
21.           if (count > 1)
22.           {
23.             
24.             sb.Append(current);
25.             sb.Append((char)(count + 127));
26.           }
27.           else
28.             sb.Append(current);
29.           count = 1;
30.           current = s[i];
31.         }
32.       }
33.       if (count > 1)
34.       {
35.         {
36.           
37.           sb.Append(current);
38.           sb.Append((char)(count+127));
39.         }          
40.       }
41.       else
42.         sb.Append(current);  
43.       return sb.ToString();
44.     }

Inspecting the string, we see the result:

[0]    97 'a'    char
[1]    130 '‚'    char
[2]    98 'b'    char
[3]    129 ''    char
[4]    97 'a'    char
[5]    99 'c'    char