# Length of minimized Compressed String

Given a string **S**, the task is to find the length of the shortest compressed string. The string can be compressed in the following way:

- If S =
**“ABCDABCD”**, then the string can be compressed as**(ABCD)**, so the length of the compressed string will be^{2}**4**. - If S =
**“AABBCCDD”**then the string compressed form will be**A**therefore, the length of the compressed string will be^{2}B^{2}C^{2}D^{2}**4**.

**Examples:**

Input:S = “aaba”Output:3Explanation :It can be rewritten as a^{2}ba therefore the answer will be 3.

Input:S = “aaabaaabccdaaabaaabccd”Output:4Explanation:The string can be rewritten as (((a)^{3}b)^{2}(c)^{2}d)^{2}. Therefore, the answer will be 4.

**Approach**: The problem can be solved using dynamic programming because it has Optimal Substructure and Overlapping Subproblems. Follow the steps below to solve the problem:

- Initialize a
**dp[][]**vector, where**dp[i][j]**stores the length of compressed substring**s[i], s[i+1], …, s[j].** - Iterate in the range
**[1, N]**using the variable**l**and perform the following steps:- Iterate in the range
**[0, N-l]**using the variable**i**and perform the following steps:- Initialize a variable say,
**j**as**i+l-1.** - If
**i**is equal to**j,**then**dp[i][j]**as**1**and**continue**. - Iterate in the range
**[i, j-1]**using the variable**k**and update**dp[i][j]**as**dp[i][j]**and**dp[i][k] + dp[k][j].** - Initialize a variable say,
**temp**as**s.substr(i, l).** - Then, find the longest prefix that is also the suffix of the substring
**temp**. - If the substring is of the form of
**dp[i][k]^n(l%(l – pref[l-1]) = 0)**, then update the value of**dp[i][j]**as**min(dp[i][j], dp[i][i + (l-pref[l-1] – 1)]).**

- Initialize a variable say,

- Iterate in the range
- Finally, print the value of
**dp[0][N-1]**as the answer.

Below is the implementation of the above approach:

## C++

`// C++ program for the above approach` ` ` `#include <bits/stdc++.h>` `using` `namespace` `std;` ` ` `// Prefix function to calculate` `// longest prefix that is also` `// the suffix of the substring S` `vector<` `int` `> prefix_function(string s)` `{` ` ` ` ` `int` `n = (` `int` `)s.length();` ` ` ` ` `vector<` `int` `> pi(n);` ` ` ` ` `for` `(` `int` `i = 1; i < n; i++) {` ` ` ` ` `int` `j = pi[i - 1];` ` ` ` ` `while` `(j > 0 && s[i] != s[j])` ` ` `j = pi[j - 1];` ` ` `if` `(s[i] == s[j])` ` ` `j++;` ` ` `pi[i] = j;` ` ` `}` ` ` ` ` `return` `pi;` `}` ` ` `// Function to find the length of the` `// shortest compressed string` `void` `minLength(string s, ` `int` `n)` `{` ` ` `// Declare a 2D dp vector` ` ` `vector<vector<` `int` `> > dp(n + 1, vector<` `int` `>(n + 1, 10000));` ` ` ` ` `// Traversing substring on the basis of length` ` ` `for` `(` `int` `l = 1; l <= n; l++) {` ` ` `// For loop for each substring of length l` ` ` `for` `(` `int` `i = 0; i < n - l + 1; i++) {` ` ` `// Second substring coordinate` ` ` `int` `j = i + l - 1;` ` ` ` ` `// If the length of the string is 1` ` ` `// then dp[i][j] = 1` ` ` `if` `(i == j) {` ` ` `dp[i][j] = 1;` ` ` `continue` `;` ` ` `}` ` ` ` ` `// Finding smallest dp[i][j] value` ` ` `// by breaking it in two substrings` ` ` `for` `(` `int` `k = i; k < j; k++) {` ` ` `dp[i][j] = min(dp[i][j],` ` ` `dp[i][k] + dp[k + 1][j]);` ` ` `}` ` ` ` ` `// Substring starting with i of length L` ` ` `string temp = s.substr(i, l);` ` ` ` ` `// Prefix function of the substring temp` ` ` `auto` `pref = prefix_function(temp);` ` ` ` ` `// Checking if the substring is` ` ` `// of the form of dp[i][k]^n` ` ` `if` `(l % (l - pref[l - 1]) == 0) {` ` ` `// If yes, check if dp[i][k] is` ` ` `// less than dp[i][j]` ` ` `dp[i][j] = min(dp[i][j],` ` ` `dp[i][i + (l - pref[l - 1] - 1)]);` ` ` `}` ` ` `}` ` ` `}` ` ` ` ` `// Finally, print the required answer` ` ` `cout << dp[0][n - 1] << endl;` `}` ` ` `// Driver Code` `int` `main()` `{` ` ` `// Given Input` ` ` `int` `n = 4;` ` ` `string s = ` `"aaba"` `;` ` ` ` ` `// Function Call` ` ` `minLength(s, n);` `}` |

**Output:**

3

**Time Complexity: **O(N^3)**Auxiliary Space: **O(N^2)

Attention reader! Don’t stop learning now. Get hold of all the important DSA concepts with the **DSA Self Paced Course** at a student-friendly price and become industry ready. To complete your preparation from learning a language to DS Algo and many more, please refer **Complete Interview Preparation Course****.**

In case you wish to attend **live classes **with experts, please refer **DSA Live Classes for Working Professionals **and **Competitive Programming Live for Students**.