Encoded String With Shortest Length LeetCode Solution

Difficulty Level Hard
Frequently asked in Amazon Google Microsoft
HuaweiViews 2130

Problem Statement

Encoded String With Shortest Length LeetCode Solution – 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.

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.

Explanation

General ideas:

We use a 2-dimension storage dp[first][count] to store the shortest encoded string of s[first ... first+count-1]. Therefore, our ultimate goal is to find dp[0][N], where N is the length of s.

For any first and count, dp[first][count] must be one of the following two cases:

  • Case 1: dp[first][count] is in the form of k[***]. In this case, dp[first][count] can be generated by repeating a substring.
  • Case 2: dp[first][count] is NOT in the form of k[***]. In this case, dp[first][count] can be generated by concatenating two substrings. Let the length of the two substrings be count1 and count - count1, we havedp[first][count] = dp[first][count1] + dp[first+count1][count – count1]

Due to the analysis of Case 2, in order to calculate our ultimate goal dp[0][N], we may need to use dp[first][count] (0<=first<N, 1<=count<=N-first). When using these values, we use memorized dynamic programming.

  • If dp[first][count] has been not yet calculated before, it equals the default value (i.e. the empty string). In this case, we calculate dp[first][count] accordingly.
  • If dp[first][count] has been calculated before, it does not equal the default value. In this case, we do not need to calculate dp[first][count].

Code

Java Code For  Encoded String With Shortest Length

class Solution {

public String encode(String s) {
    String[][] dp = new String[s.length()][s.length()];
    
    for(int l=0;l<s.length();l++) {
        for(int i=0;i<s.length()-l;i++) {
            int j = i+l;
            String substr = s.substring(i, j+1);
            // Checking if string length < 5. In that case, we know that encoding will not help.
            if(j - i < 4) {
                dp[i][j] = substr;
            } else {
                dp[i][j] = substr;
                // Loop for trying all results that we get after dividing the strings into 2 and combine the   results of 2 substrings
                for(int k = i; k<j;k++) {
                    if((dp[i][k] + dp[k+1][j]).length() < dp[i][j].length()){
                        dp[i][j] = dp[i][k] + dp[k+1][j];
                    }
                }
                
                // Loop for checking if string can itself found some pattern in it which could be repeated.
                for(int k=0;k<substr.length();k++) {
                    String repeatStr = substr.substring(0, k+1);
                    if(repeatStr != null 
                       && substr.length()%repeatStr.length() == 0 
                       && substr.replaceAll(repeatStr, "").length() == 0) {
                          String ss = substr.length()/repeatStr.length() + "[" + dp[i][i+k] + "]";
                          if(ss.length() < dp[i][j].length()) {
                            dp[i][j] = ss;
                          }
                     }
                }
            }
        }
    }
    
    return dp[0][s.length()-1];
}
}

Python Code For  Encoded String With Shortest Length

class Solution:
    
    def encode(self, s: str) -> str:
        memo = {}
        return self._get_encoded_str(s, memo)
    
    def _get_encoded_str(self, s, memo):
        if s == "" or len(s) < 5:
            return s
        if s in memo:
            return memo[s]
        chosen_str = s
        min_len = len(s)
        for i in range(1, len(s)//2 + 1):
            encoded_str = s
            prefix = s[:i]
            suffix = s[i:]
            prefix_count = self._get_prefix_count(prefix, suffix)
            encoded_prefix = self._get_encoded_str(prefix, memo)
            encoded_suffix = self._get_encoded_str(suffix, memo)
            if prefix_count > 0:
                k = prefix_count * len(prefix)
                encoded_suffix_from_k = self._get_encoded_str(suffix[k:], memo)
                encoded_str = str(prefix_count + 1) + "[" + encoded_prefix + "]" + encoded_suffix_from_k
            encoded_part_str = encoded_prefix + encoded_suffix 
            if len(encoded_str) > len(encoded_part_str):
                encoded_str = encoded_part_str
            if min_len > len(encoded_str):
                chosen_str = encoded_str
                min_len = len(encoded_str)
        memo[s] = chosen_str
        return chosen_str

    """
    Helper method finds the count of prefix in suffix.
    """
    def _get_prefix_count(self, prefix, suffix):
        count = 0
        i = 0
        while i < len(suffix):
            j = suffix.find(prefix, i)
            if i != j:
                break
            count += 1
            i = j + len(prefix)
        return count

Complexity Analysis for Encoded String With Shortest Length LeetCode Solution

Time: O(N^3)
update each value of dp[first][count] require at most O(N) time.
There are O(N^2) such values.
So overall time complexity is O(N^3).

Space: O(N^2)
The space of dp[][] is O(N^2).

Reference: https://en.wikipedia.org/wiki/Dynamic_programming

Translate »