Given a string str of lowercase alphabets, the task is to remove minimum characters from the given string so that string can be break into 3 substrings str1, str2, and str3 such that each substring can be empty or can contains only characters ‘a’, ‘b’, and ‘c’ respectively.
Example:
Input: str = “aaaabaaxccac”
Output: 3
Explanation:
String after removing b, x, and a then, string str become “aaaaaaccc”
Now str1 = “aaaaaa”, str2 = “”, str3 = “ccc”.
The minimum character removed is 3.
Input: str = “baabcbbdcca”
Output: 4
Explanation:
String after removing b, c, d, and a then, string str become “aabbbcc”
Now str1 = “aa”, str2 = “bbb”, str3 = “cc”.
The minimum character removed is 4.
Approach: This problem can be solved using Greedy Approach. We will use three prefix array to make prefix array of characters ‘a’, ‘b’, and ‘c’. Each prefix array will store the count of letter ‘a’, ‘b’, and ‘c’ at any index i respectively. Below are the steps:
- Create three prefix array as:
- prefa[i] represents the count of letter “a” in prefix of length i.
- prefb[i] represents the count of letter “b” in prefix of length i.
- prefc[i] represents the count of letter “c” in prefix of length i.
- In order to delete minimum number of character, the resultant string should be of maximum size.
- The idea is to fix two positions i and j in string, 0 ? i ? j ≤ N, in order to split string into three parts of all possible length and do the following:
- Remove all character except ‘a’ from the prefix, which ends in i, this will be the string str1.
- Remove all character except ‘c’ from the suffix, which starts in j, this will be the string str3.
- Remove all character except ‘b’ which is between positions i and j, this will be the string str2.
- Therefore, the total length of the resultant string is given by:
total length of (str1 + str2 + str3) = (prefa[i]) + (prefb[j] – prefb[i]) + (prefc[n] – prefc[j])
- Subtract the length of the resultant string from the length of the given string str to get the minimum characters to removed.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function that counts minimum// character that must be removedvoid min_remove(string str){ // Length of string int N = str.length(); // Create prefix array int prefix_a[N + 1]; int prefix_b[N + 1]; int prefix_c[N + 1]; // Initialize first position prefix_a[0] = 0; prefix_b[0] = 0; prefix_c[0] = 0; // Fill prefix array for (int i = 1; i <= N; i++) { prefix_a[i] = prefix_a[i - 1] + (str[i - 1] == 'a'); prefix_b[i] = prefix_b[i - 1] + (str[i - 1] == 'b'); prefix_c[i] = prefix_c[i - 1] + (str[i - 1] == 'c'); } // Initialise maxi int maxi = INT_MIN; // Check all the possibilities by // putting i and j at different // position & find maximum among them for (int i = 0; i <= N; i++) { for (int j = i; j <= N; j++) { maxi = max(maxi, (prefix_a[i] + (prefix_b[j] - prefix_b[i]) + (prefix_c[N] - prefix_c[j]))); } } // Print the characters to be removed cout << (N - maxi) << endl;}// Driver Codeint main(){ // Given String string str = "aaaabaaxccac"; // Function Call min_remove(str); return 0;} |
Java
// Java program for the above approach class GFG{ // Function that counts minimum // character that must be removed static void min_remove(String str) { // Length of string int N = str.length(); // Create prefix array int []prefix_a = new int[N + 1]; int []prefix_b = new int[N + 1]; int []prefix_c = new int[N + 1]; // Initialize first position prefix_a[0] = 0; prefix_b[0] = 0; prefix_c[0] = 0; // Fill prefix array for(int i = 1; i <= N; i++) { prefix_a[i] = prefix_a[i - 1] + (int)((str.charAt( i - 1) == 'a') ? 1 : 0); prefix_b[i] = prefix_b[i - 1] + (int)((str.charAt(i - 1) == 'b') ? 1 : 0); prefix_c[i] = prefix_c[i - 1] + (int)((str.charAt(i - 1) == 'c') ? 1 : 0); } // Initialise maxi int maxi = Integer.MIN_VALUE; // Check all the possibilities by // putting i and j at different // position & find maximum among them for(int i = 0; i <= N; i++) { for(int j = i; j <= N; j++) { maxi = Math.max(maxi, (prefix_a[i] + (prefix_b[j] - prefix_b[i]) + (prefix_c[N] - prefix_c[j]))); } } // Print the characters to be removed System.out.println((N - maxi)); } // Driver Code public static void main(String []args) { // Given String String str = "aaaabaaxccac"; // Function call min_remove(str); } }// This code is contributed by grand_master |
Python3
# Python 3 program for the above approachimport sys # Function that counts minimum# character that must be removeddef min_remove(st): # Length of string N = len(st) # Create prefix array prefix_a = [0]*(N + 1) prefix_b = [0]*(N + 1) prefix_c = [0]*(N + 1) # Initialize first position prefix_a[0] = 0 prefix_b[0] = 0 prefix_c[0] = 0 # Fill prefix array for i in range(1, N + 1): if (st[i - 1] == 'a'): prefix_a[i] = (prefix_a[i - 1] + 1) else: prefix_a[i] = prefix_a[i - 1] if (st[i - 1] == 'b'): prefix_b[i] = (prefix_b[i - 1] + 1) else: prefix_b[i]= prefix_b[i - 1] if (st[i - 1] == 'c'): prefix_c[i] = (prefix_c[i - 1] + 1) else: prefix_c[i] = prefix_c[i - 1] # Initialise maxi maxi = -sys.maxsize -1; # Check all the possibilities by # putting i and j at different # position & find maximum among them for i in range( N + 1): for j in range(i, N + 1): maxi = max(maxi, (prefix_a[i] + (prefix_b[j] - prefix_b[i]) + (prefix_c[N] - prefix_c[j]))) # Print the characters to be removed print((N - maxi))# Driver Codeif __name__ == "__main__": # Given String st = "aaaabaaxccac" # Function Call min_remove(st)# This code is contributed by Chitranayal |
C#
// C# program for the above approachusing System;class GFG{ // Function that counts minimum // character that must be removed static void min_remove(string str) { // Length of string int N = str.Length; // Create prefix array int []prefix_a = new int[N + 1]; int []prefix_b = new int[N + 1]; int []prefix_c = new int[N + 1]; // Initialize first position prefix_a[0] = 0; prefix_b[0] = 0; prefix_c[0] = 0; // Fill prefix array for(int i = 1; i <= N; i++) { prefix_a[i] = prefix_a[i - 1] + (int)((str[i - 1] == 'a') ? 1 : 0); prefix_b[i] = prefix_b[i - 1] + (int)((str[i - 1] == 'b') ? 1 : 0); prefix_c[i] = prefix_c[i - 1] + (int)((str[i - 1] == 'c') ? 1 : 0); } // Initialise maxi int maxi = Int32.MinValue; // Check all the possibilities by // putting i and j at different // position & find maximum among them for(int i = 0; i <= N; i++) { for(int j = i; j <= N; j++) { maxi = Math.Max(maxi, (prefix_a[i] + (prefix_b[j] - prefix_b[i]) + (prefix_c[N] - prefix_c[j]))); } } // Print the characters to be removed Console.WriteLine((N - maxi)); } // Driver Code public static void Main() { // Given String string str = "aaaabaaxccac"; // Function call min_remove(str); } }// This code is contributed by sanjoy_62 |
Javascript
<script>// JavaScript program to implement// the above approach// Function that counts minimum // character that must be removed function min_remove(str) { // Length of string let N = str.length; // Create prefix array let prefix_a = Array.from({length: N + 1}, (_, i) => 0); let prefix_b = Array.from({length: N + 1}, (_, i) => 0); let prefix_c = Array.from({length: N + 1}, (_, i) => 0); // Initialize first position prefix_a[0] = 0; prefix_b[0] = 0; prefix_c[0] = 0; // Fill prefix array for(let i = 1; i <= N; i++) { prefix_a[i] = prefix_a[i - 1] + ((str[ i - 1] == 'a') ? 1 : 0); prefix_b[i] = prefix_b[i - 1] + ((str[i - 1] == 'b') ? 1 : 0); prefix_c[i] = prefix_c[i - 1] + ((str[i - 1] == 'c') ? 1 : 0); } // Initialise maxi let maxi = Number.MIN_VALUE; // Check all the possibilities by // putting i and j at different // position & find maximum among them for(let i = 0; i <= N; i++) { for(let j = i; j <= N; j++) { maxi = Math.max(maxi, (prefix_a[i] + (prefix_b[j] - prefix_b[i]) + (prefix_c[N] - prefix_c[j]))); } } // Print the characters to be removed document.write((N - maxi)); }// Driver code // Given String let str = "aaaabaaxccac"; // Function call min_remove(str); // This code is contributed by code_hunt.</script> |
Output:
3
Time Complexity: O(N2), where N is the length of the given string.
Space Complexity: O(N), where N is the length of the given string.
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!
