Shortest String Compression Using a Doubling Macro Character
Given a string s, compress it using regular characters and a special '*' character. The '*' acts as a macro that repeats the entire sequence generated up to that point exactly once (effectively doubling it). Find the shortest possible encoded string that decodes back to s using this rule. Example: s = "ABABCABABCE" → "AB*C*E" ("AB" → "ABAB" via '*' → "ABABC" → "ABABCABABC" via '*' → "ABABCABABCE").
Question Timeline
See when this question was last asked and where, including any notes left by other candidates.
Late September, 2026
Problem Description Hermione is brewing a magic potion and needs to write down the recipe as efficiently as possible. You are given a string s representing the sequence of actions/ingredients. - To compress the instructions, you can use a special multiplier character, *. - The * character acts as a magic macro: it repeats the entire sequence of characters generated up to that point exactly once. - Your goal is to find the shortest possible encoded string using this compression rule. - Input: s = "ABABCABABCE"Output: "AB*C*E"
Hello Interview Premium
Your account is free and you can post anonymously if you choose.