Length of minimized Compressed String

0 0 8 minutes read

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 4.
If S = “AABBCCDD” then the string compressed form will be A²B²C²D² therefore, the length of the compressed string will be 4.

Examples:

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

Input: S = “aaabaaabccdaaabaaabccd”
Output: 4
Explanation: The string can be rewritten as (((a)³b)²(c)²d)². 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 update dp[i][j] as 1 and continue.
  - Iterate in the range [i, j-1] using the variable k and update dp[i][j] as min of 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)]).
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);
}

Java

/*package whatever //do not write package name here */
import java.io.*;
import java.util.*;
 
class GFG {
  // Java program for the above approach
 
  // Prefix function to calculate
  // longest prefix that is also
  // the suffix of the substring S
  static int[] prefix_function(String s)
  {
 
    int n = s.length();
 
    int[] pi = new int[n];
 
    for (int i = 1; i < n; i++) {
 
      int j = pi[i - 1];
 
      while (j > 0 && s.charAt(i) != s.charAt(j))
        j = pi[j - 1];
      if (s.charAt(i) == s.charAt(j))
        j++;
      pi[i] = j;
    }
 
    return pi;
  }
 
  // Function to find the length of the
  // shortest compressed string
  static void minLength(String s, int n)
  {
    // Declare a 2D dp vector
    int dp[][] = new int[n + 1][n + 1];
    for(int[] row : dp){
      Arrays.fill(row, 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] = Math.min(dp[i][j],
                              dp[i][k] + dp[k + 1][j]);
        }
 
        // Substring starting with i of length L
        String temp = s.substring(i, i+l);
 
        // Prefix function of the substring temp
        int[] 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] = Math.min(dp[i][j],
                              dp[i][i + (l - pref[l - 1] - 1)]);
        }
      }
    }
 
    // Finally, print the required answer
    System.out.println(dp[0][n - 1]);
  }
 
  // Driver Code
  public static void main(String args[])
  {
    // Given Input
    int n = 4;
    String s = "aaba";
 
    // Function Call
    minLength(s, n);
  }
}
 
// This code is contributed by shinjanpatra

Python3

# Python program for the above approach
 
# Prefix function to calculate
# longest prefix that is also
# the suffix of the substring S
def prefix_function(s):
 
    n = len(s)
 
    pi = [0 for i in range(n)]
 
    for i in range(1,n):
 
        j = pi[i - 1]
 
        while (j > 0 and s[i] != s[j]):
            j = pi[j - 1]
        if (s[i] == s[j]):
            j += 1
        pi[i] = j
 
    return pi
 
# Function to find the length of the
# shortest compressed string
def minLength(s,n):
 
    # Declare a 2D dp vector
    dp = [[10000 for col in range(n+1)] for row in range(n + 1)]
 
    # Traversing substring on the basis of length
    for l in range(1,n+1):
        # For loop for each substring of length l
        for i in range(n - l + 1):
            # Second substring coordinate
            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 k in range(i,j):
                dp[i][j] = min(dp[i][j],dp[i][k] + dp[k + 1][j])
 
            # Substring starting with i of length L
            temp = s[i:i+l]
 
            # Prefix function of the substring temp
            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
    print(dp[0][n - 1])
 
# Driver Code
 
# Given Input
n = 4
s = "aaba"
 
# Function Call
minLength(s, n)
 
# This code is contributed by shinjanpatra

C#

// C# program to implement above approach
using System;
using System.Collections.Generic;
 
class GFG
{
   
  // Prefix function to calculate
  // longest prefix that is also
  // the suffix of the substring S
  static int[] prefix_function(String s)
  {
 
    int n = s.Length;
 
    int[] pi = new int[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
  static void minLength(String s, int n)
  {
    // Declare a 2D dp vector
    int[][] dp = new int[n + 1][];
    for(int i = 0 ; i <= n ; i++){
      dp[i] = new int[n+1];
    }
 
    foreach(int[] row in dp){
      for(int i = 0 ; i < row.Length ; i++){
        row[i] = 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] = Math.Min(dp[i][j], dp[i][k] + dp[k + 1][j]);
        }
 
        // Substring starting with i of length L
        String temp = s.Substring(i, l);
 
        // Prefix function of the substring temp
        int[] 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] = Math.Min(dp[i][j], dp[i][i + (l - pref[l - 1] - 1)]);
        }
      }
    }
 
    // Finally, print the required answer
    Console.Write(dp[0][n - 1]);
  }
 
  // Driver Code
  public static void Main(string[] args){
 
    int n = 4;
    String s = "aaba";
 
    // Function Call
    minLength(s, n);
 
  }
}
 
// This code is contributed by subhamgoyal2014.

Javascript

<script>
 
// JavaScript program for the above approach
 
// Prefix function to calculate
// longest prefix that is also
// the suffix of the substring S
function prefix_function(s)
{
 
    let n = s.length;
    let pi = new Array(n).fill(0);
 
    for (let i = 1; i < n; i++)
    {
        let 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
function minLength(s, n)
{
 
    // Declare a 2D dp vector
    let dp = new Array(n + 1).fill(10000).map(()=>new Array(n + 1).fill(10000));
 
    // Traversing substring on the basis of length
    for (let l = 1; l <= n; l++)
    {
     
        // For loop for each substring of length l
        for (let i = 0; i < n - l + 1; i++)
        {
         
            // Second substring coordinate
            let 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 (let k = i; k < j; k++) {
                dp[i][j] = Math.min(dp[i][j],dp[i][k] + dp[k + 1][j]);
            }
 
            // Substring starting with i of length L
            let temp = s.substring(i, i+l);
 
            // Prefix function of the substring temp
            let 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] = Math.min(dp[i][j],
                               dp[i][i + (l - pref[l - 1] - 1)]);
            }
        }
    }
 
    // Finally, print the required answer
    document.write(dp[0][n - 1],"</br>");
}
 
// Driver Code
 
// Given Input
let n = 4;
let s = "aaba";
 
// Function Call
minLength(s, n);
 
// This code is contributed by shinjanpatra
 
</script>

Output:

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

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!