Encoded String With Shortest Length LeetCode Solution

Difficulty Level Hard
HuaweiViews 1690

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).

Translate »