Encode String with Shortest Length in C++

Suppose we have a non-empty string; we have to encode this string such that its encoded length will be minimum.

The encoding rule is like − k[encoded_string], where the encoded_string inside [ ] is being repeated exactly k times. We have to keep in mind that k will be a positive integer and encoded string will not be empty or have extra space. We can assume that the input string contains only lowercase letters. If the encoding process does not make the string shorter, then do not encode that string.

So, if the input is like "aaaaa", then the output will be "5[a]" as "5[a]" is shorter than "aaaaa" by 1 character.

To solve this, we will follow these steps −

• Define one 2D array dp

• Define a function collapse(), this will take s, i, j,

• temp := substring of s from index (i to j - i)

• x := temp concatenate with temp

• pos = position of temp in x

• if pos >= size of temp, then −

  • return temp

• return (size of temp / pos) as string then concatenate '[' concatenate dp[i,i+pos-1] concatenate ']'

• Define a function encode(), this will take s,

• n := size of s

• dp := Define one 2D array of size n x n

• for initialize l := 1, when l <= n, update (increase l by 1), do −

  • for initialize i := 0, j := l - 1, when j < n, update (increase i by 1), (increase j by 1), do −

    • dp[i, j] := substring of s from index i to j - i

    • for initialize k := i, when k < j, update (increase k by 1), do −

      • temp := dp[i, k] + dp[k + 1, j]

      • if size of temp < size of dp[i, j], then −

        • dp[i, j] := temp

    • rep := collapse(s, i, j)

    • if size of rep <= size of dp[i, j], then −

      • dp[i, j] := rep

• return dp[0, n - 1]

Example 

Let us see the following implementation to get better understanding −

 Live Demo

#include <bits/stdc++.h> using namespace std; class Solution { public:    vector<vector<string>> dp;    string collapse(string &s, int i, int j) {       string temp = s.substr(i, j - i + 1);       string x = temp + temp;       auto pos = x.find(temp, 1);       if (pos >= temp.size())          return temp;       return to_string((temp.size() / pos)) + "[" + dp[i][i + pos - 1] + "]";    }    string encode(string s) {       int n = s.size();       dp = vector<vector<string>>(n, vector<string>(n, ""));       for (int l = 1; l <= n; l++) {          for (int i = 0, j = l - 1; j < n; i++, j++) {             dp[i][j] = s.substr(i, j - i + 1);             for (int k = i; k < j; k++) {                string temp = dp[i][k] + dp[k + 1][j];                if (temp.size() < dp[i][j].size()) {                   dp[i][j] = temp;                }             }             string rep = collapse(s, i, j);             if (rep.size() <= dp[i][j].size()) {                dp[i][j] = rep;             }          }       }       return dp[0][n - 1];    } }; main() {    Solution ob;    cout << (ob.encode("bbbbbbbbbb")); }

Input

"bbbbbbbbbb"

Output

"10[b]"