LeetCode 471: Encode String with Shortest Length Solution in Python – A Step-by-Step Guide

What Is LeetCode 471: Encode String with Shortest Length?

In LeetCode 471: Encode String with Shortest Length, you’re given a string s, and your task is to find the shortest possible encoded string by representing repeated patterns as k[substr], where k is the repetition count and substr is the repeated substring. The encoded string must decode back to s. For example, "aaa" can be "3[a]" (4 chars vs. 3), and "abababab" can be "4[ab]" (6 chars vs. 8). It’s like finding the most compact shorthand for a verbose text while keeping it readable.

Problem Statement

• Input: s (str)—input string.
• Output: str—shortest encoded string that decodes to s.
• Rules:
• Use format k[substr] for k > 1 repetitions.
• Minimize encoded length.
• Must decode to original s.

Constraints

• 1 <= s.length <= 150.
• s consists of lowercase English letters.

Examples to Get Us Started

• Input: s = "aaa"
• Output: "3[a]" (Shortest encoding).
• Input: s = "aaaaa"
• Output: "5[a]" (5 chars vs. "2[aa]a" at 6).
• Input: s = "abababab"
• Output: "4[ab]" (6 chars vs. 8).

Understanding the Problem: Shrinking the Scroll

To solve LeetCode 471: Encode String with Shortest Length in Python, we need to encode s into its shortest form by identifying and compressing repeated substrings. A naive approach—trying all possible encodings—could be O(2^n), infeasible for n = 150. The key? Use dynamic programming to build the shortest encoding by breaking the string into optimal subproblems. We’ll explore:

• Best Solution (DP with Substring Repetition): O(n³) time, O(n²) space—fast and optimal.
• Alternative Solution (Brute Force): O(2^n) time, O(n)—simple but slow.

Let’s dive into the DP solution—it’s the scribe’s shorthand magic we need.

Best Solution: Dynamic Programming with Substring Repetition

Why This Is the Best Solution

The DP with substring repetition approach is the top pick because it’s O(n³) time and O(n²) space, efficiently finding the shortest encoding by memoizing subproblem solutions and leveraging pattern repetition. It uses a 2D DP table to store the shortest encoding for each substring, checking repeats and concatenations. It’s like drafting a scroll with shorthand notes, refining it step-by-step—smart and streamlined!

How It Works

Here’s the strategy:

• Step 1: Define DP table dp[i][j] = shortest encoding of s[i:j+1].
• Step 2: Base case: single char, dp[i][i] = s[i].
• Step 3: For each substring s[i:j+1]:
• Default: s[i:j+1] as is.
• Check repetition: If s[i:j+1] = k * pattern, try k[pattern].
• Split: Try all splits at k, dp[i][j] = dp[i][k] + dp[k+1][j].
• Step 4: Return dp[0][n-1].
• Why It Works:
• DP builds from small to large substrings.
• Repetition check captures compression opportunities.

Step-by-Step Example

Example: s = "abababab"

• Init: dp[0][0] = "a", dp[1][1] = "b", etc.
• Length 2:
• "ab": dp[0][1] = "ab" (no repeat shorter than 2).
• "ba": dp[1][2] = "ba".
• Length 4:
• "abab": 2*"ab", dp[0][3] = "2[ab]" (5 vs. 4).
• Length 8:
• "abababab": 4*"ab", dp[0][7] = "4[ab]" (6 vs. 8).
• Split: dp[0][3] + dp[4][7] = "2[ab]2[ab]" (10), "4[ab]" wins.
• Result: "4[ab]".

Example: s = "aaaaa"

• dp[0][4]:
• "aaaaa": 5*"a", "5[a]" (5 vs. 5).
• Split: "2[a]3[a]" (8), "5[a]" wins.
• Result: "5[a]".

Code with Detailed Line-by-Line Explanation

Here’s the Python code, broken down clearly:

Copy codeclass Solution:
    def encode(self, s: str) -> str:
        n = len(s)
        # Step 1: DP table
        dp = [[s[i:j+1] for j in range(n)] for i in range(n)]

        # Step 2: Fill DP table
        for length in range(1, n + 1):
            for i in range(n - length + 1):
                j = i + length - 1
                substr = s[i:j+1]

                # Step 3: Check repetition
                for k in range(1, length + 1):
                    if length % k == 0:
                        pattern = s[i:i+k]
                        if substr == pattern * (length // k):
                            encoded = f"{length // k}[{dp[i][i+k-1]}]"
                            if len(encoded) < len(dp[i][j]):
                                dp[i][j] = encoded
                                break

                # Check splits
                for k in range(i, j):
                    if len(dp[i][k]) + len(dp[k+1][j]) < len(dp[i][j]):
                        dp[i][j] = dp[i][k] + dp[k+1][j]

        return dp[0][n-1]

• Line 4-5: Init dp with substrings (e.g., dp[0][0] = "a").
• Line 8-11: Iterate lengths and start indices.
• Line 13-19: Check repetition:
• If substr = k * pattern, encode as k[pattern].
• Update if shorter.
• Line 21-23: Check splits, update if shorter.
• Line 25: Return shortest encoding.
• Time Complexity: O(n³)—lengths, splits, repetition checks.
• Space Complexity: O(n²)—DP table.

It’s like a string-shrinking scribe!

Alternative Solution: Brute Force Recursion

Why an Alternative Approach?

The brute force recursion tries all encodings—O(2^n) time, O(n) space—recursively splitting and checking repetitions without memoization. It’s slow but intuitive, like drafting every possible shorthand manually. Good for small strings or learning!

How It Works

• Step 1: Recurse on s, try all splits and repetitions.
• Step 2: Build encodings, keep shortest.
• Step 3: Return result.

Step-by-Step Example

Example: s = "aaa"

• Options:
• "aaa".
• 3*"a" → "3[a]".
• Shortest: "3[a]".

Code for Brute Force

Copy codeclass Solution:
    def encode(self, s: str) -> str:
        if not s:
            return ""

        def find_repeat(s):
            n = len(s)
            for k in range(1, n + 1):
                if n % k == 0:
                    pattern = s[:k]
                    if s == pattern * (n // k):
                        return f"{n // k}[{self.encode(pattern)}]"
            return s

        min_len = s
        # Try repetition
        encoded = find_repeat(s)
        if len(encoded) < len(min_len):
            min_len = encoded

        # Try splits
        for i in range(1, len(s)):
            left = self.encode(s[:i])
            right = self.encode(s[i:])
            if len(left + right) < len(min_len):
                min_len = left + right

        return min_len

• Line 6-13: Check repetition, encode if shorter.
• Line 16-22: Try splits, update if shorter.
• Time Complexity: O(2^n)—exponential splits.
• Space Complexity: O(n)—recursion stack.

It’s a slow shorthand drafter!

Comparing the Two Solutions

• DP (Best):
• Pros: O(n³), fast, scalable.
• Cons: O(n²) space.
• Brute Force (Alternative):
• Pros: O(2^n), simple.
• Cons: Impractical for n > 20.

DP wins for efficiency.

Edge Cases and Examples

• Input: "" → "".
• Input: "a" → "a".
• Input: "abcd" → "abcd".

DP handles all well.

Complexity Recap

• DP: Time O(n³), Space O(n²).
• Brute Force: Time O(2^n), Space O(n).

DP’s the champ.

Key Takeaways

• DP: Compress with memo.
• Brute Force: Try all encodings.
• Python Tip: DP shrinks strings—see [Python Basics](/python/basics).

Final Thoughts: Shrink That String

LeetCode 471: Encode String with Shortest Length in Python is a compression conundrum. DP with repetition is your fast scribe, while brute force is a slow quill. Want more string challenges? Try LeetCode 394: Decode String or LeetCode 459: Repeated Substring Pattern. Ready to encode some scrolls? Head to Solve LeetCode 471 on LeetCode (if unlocked) and compress it today—your coding skills are shorthand-ready!