Documentation Index
Fetch the complete documentation index at: /llms.txt
Use this file to discover all available pages before exploring further.
Tested Python solution for LeetCode 471 with 12 pytest cases. Generate a practice environment with lcpy.
lcpy gen -n 471 # by problem number
lcpy gen -s encode_string_with_shortest_length # by problem name
s, encode the string such that its encoded length is the shortest.
The encoding rule is: k[encoded_string], where the encoded_string inside the square brackets is being repeated exactly k times. k should be a positive integer.
If an encoding process does not make the string shorter, then do not encode it. If there are several solutions, return any of them.
Input: s = "aaa"
Output: "aaa"
Explanation: There is no way to encode it such that it is shorter than the input string, so we do not encode it.
Input: s = "aaaaa"
Output: "5[a]"
Explanation: "5[a]" is shorter than "aaaaa" by 1 character.
Input: s = "aaaaaaaaaa"
Output: "10[a]"
Explanation: "a9[a]" or "9[a]a" are also valid solutions, both of them have the same length = 5, which is the same as "10[a]".
1 <= s.length <= 150s consists of only lowercase English letters.from functools import cache
class Solution:
# Time: O(n^4) over substring DP
# Space: O(n^3) memoized substrings
def encode(self, s: str) -> str:
@cache
def helper(sub: str) -> str:
n = len(sub)
if n <= 4:
return sub
best = sub
for k in range(1, n // 2 + 1):
if n % k == 0 and sub[:k] * (n // k) == sub:
cand = f"{n // k}[{helper(sub[:k])}]"
if len(cand) < len(best):
best = cand
for split in range(1, n):
cand = helper(sub[:split]) + helper(sub[split:])
if len(cand) < len(best):
best = cand
return best
return helper(s)
| Time | Space |
|---|---|
| O(n^4) over substring DP | O(n^3) memoized substrings |