Implement minimal RLE encode/decode with max run K
Company: Liftoff
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
Overview: This question evaluates proficiency in string parsing and compression techniques, specifically run-length encoding/decoding, pattern detection, and algorithmic optimization for producing minimal-length encodings under a maximum pattern length constraint.
Decode RLE Tokens
Constraints
- encoded is valid
- patterns contain lowercase letters only
Examples
Input: ('2aab3ab',)
Expected Output: 'aabaabababab'
Input: ('10a',)
Expected Output: 'aaaaaaaaaa'
Hints
- Digit runs start counts; letter runs form patterns.
Minimum-Length RLE Encoding with Max Pattern Length
Constraints
- s contains lowercase letters
- 1 <= K <= len(s)
Examples
Input: ('aabaabababab', 3)
Expected Output: '2aab3ab'
Input: ('aaaaa', 2)
Expected Output: '5a'
Hints
- Use dynamic programming over the start index.
- Try each pattern length and repeat count that matches the remaining suffix.