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)2, so the length of the compressed string will be 4.
- If S = “AABBCCDD” then the string compressed form will be A2B2C2D2 therefore, the length of the compressed string will be 4.
Examples:
Input: S = “aaba”
Output: 3
Explanation : It can be rewritten as a2ba therefore the answer will be 3.Input: S = “aaabaaabccdaaabaaabccd”
Output: 4
Explanation: The string can be rewritten as (((a)3b)2(c)2d)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 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)]).
- Iterate in the range [0, N-l] using the variable i and perform the following steps:
- 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 Svector<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 stringvoid 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 Codeint 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 Sdef 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 stringdef 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 Inputn = 4s = "aaba"# Function CallminLength(s, n)# This code is contributed by shinjanpatra |
C#
// C# program to implement above approachusing 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 Sfunction 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 stringfunction 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 Inputlet n = 4;let s = "aaba";// Function CallminLength(s, n);// This code is contributed by shinjanpatra</script> |
Output:
3
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
