Katkat
Back

Implement run-length encoding and decoding

DatabricksSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

This question evaluates proficiency in string manipulation and encoding algorithms, specifically run-length encoding and decoding, along with attention to edge cases such as empty inputs and single-character runs and correct handling of repetition counts.

You are given a string consisting of lowercase English letters. You need to implement run-length encoding (RLE) and its corresponding decoding.

  1. Encoding
  • Input: a string s, e.g., "aaabccccd".
  • Output: an encoded string where each maximal group of consecutive identical characters is replaced by the character followed by the count of repetitions, e.g., "a3b1c4d1".
  1. Decoding
  • Input: an RLE-encoded string as described above, which is always valid (i.e., alternates between characters and positive integer counts), e.g., "a3b1c4d1".
  • Output: the original string, e.g., "aaabccccd".

Constraints:

  • 0 <= len(s) <= 10^5 for both encoding and decoding inputs.
  • Counts in the encoded string fit in a 32-bit signed integer.

Tasks:

  • Describe how to implement encode(String s) and decode(String encoded).
  • Explain the time and space complexity of each function.
  • Consider edge cases such as empty strings and runs of length 1.