LeetCode 471: Encode String with Shortest Length Solution

Master LeetCode problem 471 (Encode String with Shortest Length), a hard challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

471. Encode String with Shortest Length

Hard

String Dynamic Programming

Problem Explanation

Explanation:

To solve this problem, we can use dynamic programming. We can create a 2D array dp where dp[i][j] represents the shortest encoded string for the substring from index i to index j. We initialize dp[i][i] to be the character itself, and then we try to find shorter encoded strings by considering all possible splits of the string.

The key idea is to check if the current substring can be represented as a repeated pattern. If so, we can encode it as k[encodedPattern] where k is the number of repetitions. We iterate over all possible split positions k and check if we can encode the substrings before and after the split.

Finally, the answer will be stored in dp[0][n-1], where n is the length of the input string.

Solution Code

class Solution {
    public String encode(String s) {
        int n = s.length();
        String[][] dp = new String[n][n];
        
        for (int len = 1; len <= n; len++) {
            for (int i = 0; i + len - 1 < n; i++) {
                int j = i + len - 1;
                dp[i][j] = s.substring(i, i + len);
                
                if (len <= 4) continue;
                
                for (int k = i; k < j; k++) {
                    String left = dp[i][k];
                    String right = dp[k+1][j];
                    if (left.length() + right.length() < dp[i][j].length()) {
                        dp[i][j] = left + right;
                    }
                }
                
                String pattern = s.substring(i, j+1);
                int index = (pattern + pattern).indexOf(pattern, 1);
                if (index < pattern.length()) {
                    pattern = (pattern.length() / index) + "[" + dp[i][i+index-1] + "]";
                }
                
                if (pattern.length() < dp[i][j].length()) {
                    dp[i][j] = pattern;
                }
            }
        }
        
        return dp[0][n-1];
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 471 (Encode String with Shortest Length)?

This page provides optimized solutions for LeetCode problem 471 (Encode String with Shortest Length) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 471 (Encode String with Shortest Length)?

The time complexity for LeetCode 471 (Encode String with Shortest Length) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 471 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 471 in Java, C++, or Python.

Back to LeetCode Solutions