# Encode String with Shortest Length

This page explains Java solution to problem `Encode String with Shortest Length` using `Dynamic Programming` algorithm.

## Problem Statement

Given a non-empty string, 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` will 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 = "aaaaa"
Output: "5[a]"
Explanation: "5[a]" is shorter than "aaaaa" by 1 character.

Example 2:

Input: s = "abbbabbbcabbbabbbc"
Output: "2[2[abbb]c]"
Explanation: "abbbabbbc" occurs twice, but "abbbabbbc" can also be encoded to "2[abbb]c", so one answer can be "2[2[abbb]c]".

## Solution

If you have any suggestions in below code, please create a pull request by clicking here.
``````
package com.vc.hard;

class EncodeStringWithShortestLength {
public String encode(String s) {
if(s == null || s.length() == 0) return "";

int n = s.length();
String[][] dp = new String[n][n];
for(int len = 0; len < s.length(); len++) {
for(int from = 0; from + len < s.length(); from++) {
int to = from + len;

String subStr = s.substring(from, to + 1);
dp[from][to] = subStr;

if(to - from < 4) continue;

//See if length is less if we combine two half
for(int middle = from; middle < to; middle++) {
int length = (dp[from][middle] + dp[middle + 1][to]).length();
if(length < dp[from][to].length()) {
dp[from][to] = dp[from][middle] + dp[middle + 1][to];
}
}

//See if we can find any repeat String
int index = (subStr + subStr).indexOf(subStr, 1);

if(index < subStr.length()) {
subStr = subStr.length() / index + "["+dp[from][from + index - 1]+"]";
}

if(subStr.length() < dp[from][to].length()) {
dp[from][to] = subStr;
}
}
}
return dp[n - 1];
}
}
``````

## Time Complexity

O(N3) Where
N is length of input string

## Space Complexity

O(N2) Where
N is length of input string