Run Length Encoding Problems

Question

Given a run-length encoded string (e.g., the array {'B','A','A','E','E','E','C'} is encoded as the string "B1A2E3C1"), implement the following using only the encoded representation:
1. `char Find(int p)`: Return the character at position `p` in the original (unencoded) data.
2. Follow-up — `char FindByValue(char target, int left, int right)`: Find the lexicographically largest character within the index range [left, right] of the original data. The input data is assumed to be sorted.

AceOffer · Accepted Answer

Given a run-length encoded string (e.g., the array {'B','A','A','E','E','E','C'} is encoded as the string "B1A2E3C1"), implement the following using only the encoded representation:
1. `char Find(int p)`: Return the character at position `p` in the original (unencoded) data.
2. Follow-up — `char FindByValue(char target, int left, int right)`: Find the lexicographically largest character within the index range [left, right] of the original data. The input data is assumed to be sorted.

Reported follow-ups:
1. Implement `char FindByValue(char target, int left, int right)` that finds the lexicographically largest character in the range [left, right] of the original data. The input is assumed to be sorted. (when: After candidate solves Find(int p))

**Alternative approaches:** Prefix sum array / precomputed offsets (Precompute cumulative counts for all runs into an array, then use binary search to answer each Find query in O(log n) instead of O(n) linear scan; costs O(n) extra space where n is number of runs.)

Run Length Encoding Problems

Problem Overview

Follow-up Arc

Approach Trade-offs

Practice