Encode String with Shortest Length - Solution & Explanation

Q: Is Encode String with Shortest Length easy or hard?

Encode String with Shortest Length is classified as Hard because it combines substring dynamic programming with pattern compression logic. Many candidates struggle with recognizing the DP state definition and efficiently detecting repeating substrings.

Q: Encode String with Shortest Length Python/Java solution

Most implementations use a DP matrix where dp[i][j] stores the best encoding for substring s[i..j]. For each substring, iterate through split points and also check if the substring is composed of repeating units. This approach translates cleanly into Python, Java, C++, Go, and TypeScript using nested loops and substring checks.

Q: How to solve Encode String with Shortest Length in O(n)?

An O(n) solution is not known for the general version of this problem because you must evaluate many substring combinations to guarantee the shortest encoding. The commonly accepted optimal solution uses dynamic programming with O(n^3) time. Faster heuristics may detect repetitions quickly but cannot guarantee optimal compression for all cases.

Q: What is the best approach for Encode String with Shortest Length?

Dynamic programming on substrings combined with repetition detection is the best approach. Build a DP table where dp[i][j] stores the shortest encoding of substring s[i..j]. Try splitting the substring and also check if it consists of repeated patterns that can be encoded as k[pattern]. This guarantees the minimal encoded string with O(n^3) time complexity.

Q: Is Encode String with Shortest Length asked at Google/Amazon/Meta?

Encode String with Shortest Length is considered a high‑difficulty string and dynamic programming problem and has appeared in advanced interview preparation sets used by companies like Google and Meta. It tests substring DP, pattern detection, and optimization of overlapping subproblems.

Q: What data structure is used in Encode String with Shortest Length?

The core data structure is a 2D dynamic programming table where each cell stores the shortest encoded string for a substring. String operations and substring comparisons are used heavily to detect repetition patterns and construct compressed forms.

Q: What is the time complexity of Encode String with Shortest Length?

The optimal solution runs in O(n^3) time and O(n^2) space. The algorithm evaluates every substring, tries all possible split points, and checks for repeating patterns inside each substring. Since there are O(n^2) substrings and up to O(n) split operations per substring, the total time becomes cubic.

HardPremiumFree on FleetCodeString Dynamic Programming5 min readAsked at: Google

Practice this problem

Problem Statement

Given a string 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.

Example 1:

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.

Example 2:

Input: s = "aaaaa"
Output: "5[a]"
Explanation: "5[a]" is shorter than "aaaaa" by 1 character.

Example 3:

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]".

Constraints:

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

Approach Overview

Problem Overview: You receive a string and must encode it into the shortest possible representation using the pattern k[encoded_string], where the substring inside brackets repeats exactly k times. The goal is to minimize the final encoded length while preserving the original string when decoded.

Approach 1: Brute Force Substring Enumeration (Exponential Time, O(2^n) time, O(n) space)

Generate every possible partition of the string and attempt to compress repeating segments using the k[pattern] format. For each substring, check if it consists of repeated copies of a smaller substring. This approach repeatedly recomputes encodings for the same substrings and quickly becomes infeasible as string length grows. It helps illustrate the core idea of detecting repetition but does not scale beyond small inputs.

Approach 2: Dynamic Programming on Substrings (O(n^3) time, O(n^2) space)

Define dp[i][j] as the shortest encoded string for substring s[i..j]. Iterate over substring lengths and try every split point k between i and j, combining dp[i][k] and dp[k+1][j]. Then check if the entire substring is a repetition of some smaller pattern. If it is, encode it as count[encoded_pattern]. This avoids recomputation because every substring result is stored and reused. The nested substring iteration leads to O(n^3) time complexity.

Approach 3: DP with Efficient Repetition Detection (O(n^3) time, O(n^2) space)

Use the same DP table but detect repeating patterns efficiently. For substring t, compute (t + t).find(t, 1) to determine whether a shorter repeating unit exists. If the index returned is less than the substring length, the substring is periodic and can be encoded as k[dp[i][i+pattern_len-1]]. This trick quickly identifies repeating structures like ababab or aaaa. Combined with DP splitting, it guarantees the globally shortest encoding.

Recommended for interviews: The dynamic programming approach with substring repetition detection is the expected solution. It demonstrates strong understanding of dynamic programming and efficient pattern detection within string problems. Explaining the brute force idea first shows intuition, but implementing the dp[i][j] solution proves you can optimize overlapping subproblems and recognize repeated string structures.

Solution

Code

Python Java C++Go TypeScript

Python

Java

C++

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

Approach	Time	Space	When to Use
Brute Force Substring Encoding	O(2^n)	O(n)	Conceptual understanding of repetition detection; impractical for large inputs
Dynamic Programming with Split Enumeration	O(n^3)	O(n^2)	General solution that guarantees shortest encoding
DP with Repetition Detection Trick	O(n^3)	O(n^2)	Best practical approach; quickly detects repeating patterns and minimizes encoded length

Video Solution

LeetCode 471. Encode String with Shortest Length • Happy Coding • 4,893 views views

Watch 2 more video solutions →

Frequently Asked Questions

Is Encode String with Shortest Length easy or hard?

Encode String with Shortest Length is classified as Hard because it combines substring dynamic programming with pattern compression logic. Many candidates struggle with recognizing the DP state definition and efficiently detecting repeating substrings.

Encode String with Shortest Length Python/Java solution

Most implementations use a DP matrix where dp[i][j] stores the best encoding for substring s[i..j]. For each substring, iterate through split points and also check if the substring is composed of repeating units. This approach translates cleanly into Python, Java, C++, Go, and TypeScript using nested loops and substring checks.

How to solve Encode String with Shortest Length in O(n)?

An O(n) solution is not known for the general version of this problem because you must evaluate many substring combinations to guarantee the shortest encoding. The commonly accepted optimal solution uses dynamic programming with O(n^3) time. Faster heuristics may detect repetitions quickly but cannot guarantee optimal compression for all cases.

What is the best approach for Encode String with Shortest Length?

Dynamic programming on substrings combined with repetition detection is the best approach. Build a DP table where dp[i][j] stores the shortest encoding of substring s[i..j]. Try splitting the substring and also check if it consists of repeated patterns that can be encoded as k[pattern]. This guarantees the minimal encoded string with O(n^3) time complexity.

Is Encode String with Shortest Length asked at Google/Amazon/Meta?

Encode String with Shortest Length is considered a high‑difficulty string and dynamic programming problem and has appeared in advanced interview preparation sets used by companies like Google and Meta. It tests substring DP, pattern detection, and optimization of overlapping subproblems.

What data structure is used in Encode String with Shortest Length?

The core data structure is a 2D dynamic programming table where each cell stores the shortest encoded string for a substring. String operations and substring comparisons are used heavily to detect repetition patterns and construct compressed forms.

What is the time complexity of Encode String with Shortest Length?

The optimal solution runs in O(n^3) time and O(n^2) space. The algorithm evaluates every substring, tries all possible split points, and checks for repeating patterns inside each substring. Since there are O(n^2) substrings and up to O(n) split operations per substring, the total time becomes cubic.

Ready to solve this problem?

Practice Encode String with Shortest Length with our built-in code editor and test cases.

Practice on FleetCode

Decode String

Number of Atoms

Problem Info

DifficultyHard

Acceptance50.5%

Approaches1

Reading time5 min

Asked at

Google