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.
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:
char Find(int p): Return the character at position p in the original (unencoded) data.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.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))
| Approach | Notes |
|---|---|
| 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. |