Implement run-length encoding and decoding

Q: Implement run-length encoding and decoding

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.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

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

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" .
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.

Implement run-length encoding and decoding

Overview

Comments (0)