Practice/Amazon/Leetcode 471. Encode String with Shortest Length

Leetcode 471. Encode String with Shortest Length

CodingMust

Problem

You are given a non-empty string consisting of lowercase English letters. Your task is to find the shortest encoded representation of this string using a special compression notation.

The compression notation allows you to represent repeated substrings using the format k[substring], where k is a positive integer indicating how many times the substring repeats consecutively. Encodings can be nested, meaning the substring inside brackets can itself contain encoded patterns.

Your goal is to return the shortest possible encoded string. If multiple encodings have the same length, return any valid one. If no encoding is shorter than the original string, return the original string.

Requirements

1. Implement a function that takes a string and returns its shortest encoded form
2. The encoding must use the notation k[encoded_string] where k ≥ 2
3. Support nested encodings where the content inside brackets can itself be encoded
4. Only encode a pattern if the encoded form is strictly shorter than the unencoded form
5. The function must find the globally optimal encoding considering all possible splits and nestings

Constraints

• 1 ≤ length of string ≤ 150
• The string contains only lowercase English letters (a-z)
• Time complexity should be O(n³) or better where n is the length of the string
• Space complexity should be O(n²) for memoization

Examples

Example 1:

Input: s = "aaa" Output: "aaa" Explanation: Encoding as "3[a]" produces a 4-character string, which is longer than the original 3 characters.

Example 2:

Input: s = "aaaa" Output: "4[a]" Explanation: Encoding as "4[a]" produces a 4-character string, same length as original, but either answer is acceptable.

Example 3:

Input: s = "abbbabbbabbb" Output: "3[a3[b]]" Explanation: The pattern "abbb" repeats 3 times. Within "abbb", we can encode "bbb" as "3[b]", giving us "a3[b]" for each repetition. Finally, "a3[b]" repeats 3 times, so we get "3[a3[b]]" (9 characters vs 12 original).

Example 4:

Input: s = "aabcaabcd" Output: "2[aabc]d" Explanation: The prefix "aabc" repeats twice, followed by "d". Encoding gives "2[aabc]d" (9 characters vs 9 original).