Given a string S of length N, consisting of lowercase English alphabets only, the task is to find the minimum possible length of run-length-encoding that can be generated by removing at most K characters from the string S.
Examples:
Input: S = “abbbcdcdd”, N = 9, K = 2
Output: 5
Explanation: One possible way is to delete both occurrences of ‘c’ from S.
The new string generated is “abbbddd” whose run-length-encoding is “ab3d3”.
Therefore, the length of the encoded string is 5.Input: S = “aabbca”, N = 6, K = 3
Output: 2
Explanation: One possible way is to delete both the occurrences of ‘b’ and one occurrence of ‘c’.
The new string generated is “aaa” whose run-length-encoding is “a3”.
Therefore, the length of the encoded string is 2
Naive Approach: The simplest approach to solve the problem is to remove every combination of K characters from the string and calculate their respective run-length-encoding. Finally, print the length of the smallest run-length-encoding obtained.
Time Complexity: O(K * N!(N – K)! * K!)
Auxiliary Space: O(K)
Efficient Approach: To optimize the above approach, follow the steps below to solve the problem:
- Maintain an auxiliary array dp[n][k][26][n], where dp[idx][K][last][count] denotes the minimum run-length-encoding obtained starting from index idx where, K denotes the number of deletions remaining, last denotes the last character with frequency count so far.
- For every character, two possibilities exists, either to delete the character or to retain it.
- Consider that the current character at index idx is deleted and calculate recursively the minimum run-length encoding obtained by passing the parameters (idx + 1, K – 1, last, count)
- Now, consider that the current character at index idx is retained and calculate recursively the minimum run-length encoding for the following two cases:
- If S[idx] = last: Calculate minimum run-length encoding by passing the parameters (idx + 1, K, S[idx], count + 1).
- Otherwise, calculate minimum run-length encoding by passing the parameters (idx + 1, K, S[idx], 1).
- Return the minimum of the above-computed values and repeat the above steps for all indices of the string.
Below is the implementation of the above approach:
C++
// C++ Program to implement// the above approach#include <bits/stdc++.h>using namespace std;#define maxN 20int dp[maxN][maxN][27][maxN];// Function which solves the desired problemint solve(string& s, int n, int idx, int k, char last = 123, int count = 0){ // idx: current index in s // k: Remaining number of deletions // last: Previous character // count: Number of occurrences // of the previous character // Base Case if (k < 0) return n + 1; // If the entire string has // been traversed if (idx == n) return 0; int& ans = dp[idx][k][last - 'a'][count]; // If precomputed subproblem // occurred if (ans != -1) return ans; ans = n + 1; // Minimum run length encoding by // removing the current character ans = min(ans, solve(s, n, idx + 1, k - 1, last, count)); // Minimum run length encoding by // retaining the current character int inc = 0; if (count == 1 || count == 9 || count == 99) inc = 1; // If the current and the // previous characters match if (last == s[idx]) { ans = min(ans, inc + solve(s, n, idx + 1, k, s[idx], count + 1)); } // Otherwise else { ans = min(ans, 1 + solve(s, n, idx + 1, k, s[idx], 1)); } return ans;}// Function to return minimum run-length encoding// for string s by removing atmost k charactersint MinRunLengthEncoding(string& s, int n, int k){ memset(dp, -1, sizeof(dp)); return solve(s, n, 0, k);}// Driver Codeint main(){ string S = "abbbcdcdd"; int N = 9, K = 2; cout << MinRunLengthEncoding(S, N, K); return 0;} |
Java
// Java program to implement // the above approach import java.util.*;class GFG{static int maxN = 20;static int dp[][][][] = new int[maxN][maxN][27][maxN];// Function which solves the desired problempublic static int solve(String s, int n, int idx, int k, char last, int count){ // idx: current index in s // k: Remaining number of deletions // last: Previous character // count: Number of occurrences // of the previous character // Base Case if (k < 0) return n + 1; // If the entire string has // been traversed if (idx == n) return 0; int ans = dp[idx][k][last - 'a'][count]; // If precomputed subproblem // occurred if (ans != -1) return ans; ans = n + 1; // Minimum run length encoding by // removing the current character ans = Math.min(ans, solve(s, n, idx + 1, k - 1, last, count)); // Minimum run length encoding by // retaining the current character int inc = 0; if (count == 1 || count == 9 || count == 99) inc = 1; // If the current and the // previous characters match if (last == s.charAt(idx)) { ans = Math.min(ans, inc + solve(s, n, idx + 1, k, s.charAt(idx), count + 1)); } // Otherwise else { ans = Math.min(ans, 1 + solve(s, n, idx + 1, k, s.charAt(idx), 1)); } return dp[idx][k][last - 'a'][count] = ans;}// Function to return minimum run-length encoding// for string s by removing atmost k characterspublic static int MinRunLengthEncoding(String s, int n, int k){ for(int i[][][] : dp) for(int j[][] : i) for(int p[] : j) Arrays.fill(p, -1); return solve(s, n, 0, k, (char)123, 0);}// Driver Codepublic static void main(String args[]){ String S = "abbbcdcdd"; int N = 9, K = 2; System.out.println(MinRunLengthEncoding(S, N, K));}}// This code is contributed by hemanth gadarla |
Python3
# Python3 program to implement# the above approachmaxN = 20dp = [[[[0 for i in range(maxN)] for j in range(27)] for k in range(27)] for l in range(maxN)]# Function which solves the desired problemdef solve(s, n, idx, k, last, count): # idx: current index in s # k: Remaining number of deletions # last: Previous character # count: Number of occurrences # of the previous character # Base Case if (k < 0): return n + 1 # If the entire string has # been traversed if (idx == n): return 0 ans = dp[idx][k][ord(last) - ord('a')][count] # If precomputed subproblem # occurred if (ans != -1): return ans ans = n + 1 # Minimum run length encoding by # removing the current character ans = min(ans, solve(s, n, idx + 1, k - 1, last, count)) # Minimum run length encoding by # retaining the current character inc = 0 if (count == 1 or count == 9 or count == 99): inc = 1 # If the current and the # previous characters match if (last == s[idx]): ans = min(ans, inc + solve(s, n, idx + 1, k, s[idx], count + 1)) # Otherwise else: ans = max(ans, 1 + solve(s, n, idx + 1, k, s[idx], 1)) dp[idx][k][ord(last) - ord('a')][count] = ans #print(ans) return dp[idx][k][ord(last) - ord('a')][count]# Function to return minimum run-length encoding# for string s by removing atmost k charactersdef MinRunLengthEncoding(s, n, k): for i in range(maxN): for j in range(27): for k in range(27): for l in range(maxN): dp[i][j][k][l] = -1 return solve(s, n, 0, k, chr(123), 0) - 1# Driver Codeif __name__ == '__main__': S = "abbbcdcdd" N = 9 K = 2 print(MinRunLengthEncoding(S, N, K))# This code is contributed by gauravrajput1 |
C#
// C# program to implement // the above approach using System;class GFG{static int maxN = 20;static int [,,,]dp = new int[maxN, maxN, 27, maxN];// Function which solves // the desired problempublic static int solve(String s, int n, int idx, int k, char last, int count){ // idx: current index in s // k: Remaining number of deletions // last: Previous character // count: Number of occurrences // of the previous character // Base Case if (k < 0) return n + 1; // If the entire string // has been traversed if (idx == n) return 0; int ans = dp[idx, k, last - 'a', count]; // If precomputed subproblem // occurred if (ans != -1) return ans; ans = n + 1; // Minimum run length encoding by // removing the current character ans = Math.Min(ans, solve(s, n, idx + 1, k - 1, last, count)); // Minimum run length encoding by // retaining the current character int inc = 0; if (count == 1 || count == 9 || count == 99) inc = 1; // If the current and the // previous characters match if (last == s[idx]) { ans = Math.Min(ans, inc + solve(s, n, idx + 1, k, s[idx], count + 1)); } // Otherwise else { ans = Math.Min(ans, 1 + solve(s, n, idx + 1, k, s[idx], 1)); } return dp[idx, k, last - 'a', count] = ans;}// Function to return minimum // run-length encoding for string // s by removing atmost k characterspublic static int MinRunLengthEncoding(String s, int n, int k){ for (int i = 0; i < maxN; i++) for (int j = 0; j < maxN; j++) for (int p = 0; p < 27; p++) for (int l = 0; l < maxN; l++) dp[i, j, p, l] = -1; return solve(s, n, 0, k, (char)123, 0);}// Driver Codepublic static void Main(String []args){ String S = "abbbcdcdd"; int N = 9, K = 2; Console.WriteLine( MinRunLengthEncoding(S, N, K));}}// This code is contributed by 29AjayKumar |
Javascript
<script> // JavaScript program to implement the above approach let maxN = 20; let dp = new Array(maxN); // Function which solves the desired problem function solve(s, n, idx, k, last, count) { // idx: current index in s // k: Remaining number of deletions // last: Previous character // count: Number of occurrences // of the previous character // Base Case if (k < 0) return n + 1; // If the entire string has // been traversed if (idx == n) return 0; let ans = dp[idx][k][last - 'a'.charCodeAt()][count]; // If precomputed subproblem // occurred if (ans != -1) return ans; ans = n + 1; // Minimum run length encoding by // removing the current character ans = Math.min(ans, solve(s, n, idx + 1, k - 1, last, count)); // Minimum run length encoding by // retaining the current character let inc = 0; if (count == 1 || count == 9 || count == 99) inc = 1; // If the current and the // previous characters match if (last == s[idx].charCodeAt()) { ans = Math.min(ans, inc + solve(s, n, idx + 1, k, s[idx].charCodeAt(), count + 1)); } // Otherwise else { ans = Math.min(ans, 1 + solve(s, n, idx + 1, k, s[idx].charCodeAt(), 1)); } dp[idx][k][last - 'a'.charCodeAt()][count] = ans; return dp[idx][k][last - 'a'.charCodeAt()][count]; } // Function to return minimum run-length encoding // for string s by removing atmost k characters function MinRunLengthEncoding(s, n, k) { for(let i = 0; i < maxN; i++) { dp[i] = new Array(maxN); for(let j = 0; j < maxN; j++) { dp[i][j] = new Array(27); for(let k = 0; k < 27; k++) { dp[i][j][k] = new Array(maxN); for(let l = 0; l < maxN; l++) { dp[i][j][k][l] = -1; } } } } return solve(s, n, 0, k, 123, 0); } let S = "abbbcdcdd"; let N = 9, K = 2; document.write(MinRunLengthEncoding(S, N, K)); </script> |
Output:
5
Time Complexity: O(26 * N2 * K)
Auxiliary Space: O(26 * N2 * K)
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!
