Implement minimal RLE encode/decode with max run K
Problem Description
You are tasked with implementing a run-length encoding (RLE) scheme that compresses a string by grouping consecutive repetitions of a short substring. This scheme involves both encoding and decoding operations with specific constraints.
Encoding Format
An encoded string is a concatenation of tokens. Each token follows the format <count><pattern>:
count: A positive integer written in base-10. It may consist of multiple digits and does not include a+sign.pattern: A non-empty string composed solely of lowercase lettersa-z.
The decoded expansion of a token is the pattern repeated count times.
Tokens are concatenated directly. The boundaries between tokens are determined by the transition from a digit (part of count) to a letter (part of pattern), or vice-versa.
Example:
"2aab3ab" decodes to "aab" + "aab" + "ab" + "ab" + "ab" which results in "aabaabababab".
Task A — Decode
Implement the function:
decode(encoded: str) -> str
Given a valid encoded string, your function should return the original decoded string.
Task B — Encode (Optimized)
Implement the function:
encode(s: str, K: int) -> str
Your function must produce an encoded string that, when decoded, exactly matches the input string s. This task has an additional constraint and an optimization goal:
- Constraint: Every
patternused in any token within the encoded string must have a length less than or equal toK(pattern.length ≤ K). - Optimization: Among all valid encodings that satisfy the
Kconstraint, you must return one with the minimum total encoded length (i.e., the fewest characters in the resulting encoded string). If multiple shortest encodings exist, any one of them is acceptable.
Example:
For s = "aabaabababab" and K = 3, one shortest encoding is "2aab3ab". This is because it represents 2 * "aab" followed by 3 * "ab", and both patterns ("aab" and "ab") have lengths less than or equal to K=3.
Notes / Constraints
- The input string
sfor encoding contains only lowercase lettersa-z. - The value of
Kis constrained such that1 ≤ K ≤ len(s). - The
countin a token can be larger than 9, meaning it can be a multi-digit number. - Your encoding must strictly adhere to the
<count><pattern>token format; you cannot emit raw, uncounted literal characters.
AI interview prep
Core dilemma
The central engineering conflict is finding the globally optimal (minimum length) run-length encoding for a given string `s` under the constraint of a maximum pattern length `K`, where the 'count' part of the token also contributes to the encoded length.
3 tradeoffs and 3 stress tests locked
Interview prep
Unlock the interviewer X-Ray rubric, tradeoff matrix, stress tests, clarifying questions, and key concepts.
Implement minimal RLE encode/decode with max run K
Problem Description
You are tasked with implementing a run-length encoding (RLE) scheme that compresses a string by grouping consecutive repetitions of a short substring. This scheme involves both encoding and decoding operations with specific constraints.
Encoding Format
An encoded string is a concatenation of tokens. Each token follows the format <count><pattern>:
count: A positive integer written in base-10. It may consist of multiple digits and does not include a+sign.pattern: A non-empty string composed solely of lowercase lettersa-z.
The decoded expansion of a token is the pattern repeated count times.
Tokens are concatenated directly. The boundaries between tokens are determined by the transition from a digit (part of count) to a letter (part of pattern), or vice-versa.
Example:
"2aab3ab" decodes to "aab" + "aab" + "ab" + "ab" + "ab" which results in "aabaabababab".
Task A — Decode
Implement the function:
decode(encoded: str) -> str
Given a valid encoded string, your function should return the original decoded string.
Task B — Encode (Optimized)
Implement the function:
encode(s: str, K: int) -> str
Your function must produce an encoded string that, when decoded, exactly matches the input string s. This task has an additional constraint and an optimization goal:
- Constraint: Every
patternused in any token within the encoded string must have a length less than or equal toK(pattern.length ≤ K). - Optimization: Among all valid encodings that satisfy the
Kconstraint, you must return one with the minimum total encoded length (i.e., the fewest characters in the resulting encoded string). If multiple shortest encodings exist, any one of them is acceptable.
Example:
For s = "aabaabababab" and K = 3, one shortest encoding is "2aab3ab". This is because it represents 2 * "aab" followed by 3 * "ab", and both patterns ("aab" and "ab") have lengths less than or equal to K=3.
Notes / Constraints
- The input string
sfor encoding contains only lowercase lettersa-z. - The value of
Kis constrained such that1 ≤ K ≤ len(s). - The
countin a token can be larger than 9, meaning it can be a multi-digit number. - Your encoding must strictly adhere to the
<count><pattern>token format; you cannot emit raw, uncounted literal characters.