Problem statement :
if the input string is “wwwwaaadexxxxxx”, then the function should return “w4a3de1x6″
Basically Run Length Encoding.
Easiest way to do this is using a Dictionary data structure.
You travel through the string once (O(n)) and fill the dictionary as following :
Key : Char Value: Count,
so w:4, a:3, d:1, e:1, x:6.
After filling the dictionary, you can just travel through the dictionary and concat key+value to print run length encoded string.
To preserve the order you can also use LinkedHashSet<> data structure.
here is the code using Dictionary.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
private string RLE(string input) { string encoded = string.Empty; Dictionary<char, int> charToStrings = new Dictionary<char, int>(); for (int i = 0; i < input.Length; i++) { if(charToStrings.ContainsKey(input[i])) { charToStrings[input[i]]++; } else { charToStrings.Add(input[i], 1); } } foreach(KeyValuePair<char,int> pair in charToStrings) { encoded += pair.Value.ToString() + pair.Key.ToString(); } return encoded; } |