Given a string str of length N, the task is to find the minimum number of substrings required to be removed to make all the remaining characters of the string same.
Note: The substring to be removed must not contain the last remaining character in the string.
Examples:
Input: str = “ACBDAB”
Output: 2
Explanation:
Removing the substring { str[1], …, str[3] } modifies str to “AAB”
Removing the substring {str[2] } modifies str to “AA”
Since all characters of str are equal, the required output is 2.Input: str = “ZBCDEFZ”
Output: 1
Explanation:
Removing the substring { str[1], …, str[5] } modifies str to “ZZ”
Since all characters of str are equal, the required output is 1.
Approach: The idea is to first remove all the consecutive duplicate characters of the string and count the frequency of each distinct character of the string. Finally, remove all the characters of the string except the character having minimum frequency. Follow the steps below to solve the problem:
- Iterate over all the characters of the string and remove all the consecutive duplicate characters of the string.
- Count the frequency of each distinct character of the string and decrement the frequency of the first and the last character of the string by 1.
- Finally, print the minimum frequency obtained.
Below is the implementation of the above approach:
C++
// C++ program to implement// the above approach#include <bits/stdc++.h>using namespace std;// Function to count minimum operations// required to make all characters equal// by repeatedly removing substringvoid minOperationNeeded(string str){ // Remove consecutive duplicate // characters from str str = string(str.begin(), unique(str.begin(), str.end())); // Stores length of the string int N = str.length(); // Stores frequency of each distinct // characters of the string str int res[256] = { 0 }; // Iterate over all the characters // of the string str for (int i = 0; i < N; ++i) { // Update frequency of str[i] res[str[i]] += 1; } // Decrementing the frequency // of the string str[0] res[str[0]] -= 1; // Decrementing the frequency // of the string str[N - 1] res[str[N - 1]] -= 1; // Stores the required count int ans = INT_MAX; // Iterate over all characters // of the string str for (int i = 0; i < N; ++i) { // Update ans ans = min(ans, res[str[i]]); } cout << (ans + 1) << endl;}// Driver Codeint main(){ // Given string string str = "ABCDABCDABCDA"; minOperationNeeded(str); return 0;} |
Java
// Java program to implement// the above approachimport java.util.*;class GFG { // Function to count minimum operations // required to make all characters equal // by repeatedly removing subString static void minOperationNeeded(char[] str) { // Remove consecutive duplicate // characters from str str = modstring(str); // Stores length of the String int N = str.length; // Stores frequency of each distinct // characters of the String str int res[] = new int[256]; // Iterate over all the characters // of the String str for (int i = 0; i < N; ++i) { // Update frequency of str[i] res[str[i]] += 1; } // Decrementing the frequency // of the String str[0] res[str[0]] -= 1; // Decrementing the frequency // of the String str[N - 1] res[str[N - 1]] -= 1; // Stores the required count int ans = Integer.MAX_VALUE; // Iterate over all characters // of the String str for (int i = 0; i < N; ++i) { // Update ans ans = Math.min(ans, res[str[i]]); } System.out.print((ans + 1) + "\n"); } private static char[] modstring(char[] str) { String s = ""; boolean b = true; for (int i = 1; i < str.length; ++i) { if (str[i - 1] != str[i]) b = true; if (b) { s += str[i-1]; b = false; } } return s.toCharArray(); } // Driver Code public static void main(String[] args) { // Given String String str = "ABCDABCDABCDA"; minOperationNeeded(str.toCharArray()); }}// This code is contributed by Amit Katiyar |
Python3
# Python3 program to implement# the above approachimport re, sys# Function to count minimum operations# required to make all characters equal# by repeatedly removing substringdef minOperationNeeded(s): # Remove consecutive duplicate # characters from str d = {} str = re.sub(r"(.)\1 + ",'', s) # Stores length of the string N = len(str) # Stores frequency of each distinct # characters of the string str res = [0 for i in range(256)] # Iterate over all the characters # of the string str for i in range(N): # Update frequency of str[i] res[ord(str[i])] += 1 # Decrementing the frequency # of the string str[0] res[ord(str[0])] -= 1 # Decrementing the frequency # of the ord(string ord(str[N - 1] res[ord(str[N - 1])] -= 1 # Stores the required count ans = sys.maxsize # Iterate over all characters # of the string str for i in range(N): # Update ans ans = min(ans, res[ord(str[i])]) print ((ans + 1))# Driver Codeif __name__ == '__main__': # Given string str = "ABCDABCDABCDA" minOperationNeeded(str)# This code is contributed by mohit kumar 29 |
C#
// C# program for the above approach using System;class GFG{ // Function to count minimum operations // required to make all characters equal // by repeatedly removing subString static void minOperationNeeded(char[] str) { // Remove consecutive duplicate // characters from str str = modstring(str); // Stores length of the String int N = str.Length; // Stores frequency of each distinct // characters of the String str int[] res = new int[256]; // Iterate over all the characters // of the String str for (int i = 0; i < N; ++i) { // Update frequency of str[i] res[str[i]] += 1; } // Decrementing the frequency // of the String str[0] res[str[0]] -= 1; // Decrementing the frequency // of the String str[N - 1] res[str[N - 1]] -= 1; // Stores the required count int ans = Int32.MaxValue; // Iterate over all characters // of the String str for (int i = 0; i < N; ++i) { // Update ans ans = Math.Min(ans, res[str[i]]); } Console.WriteLine((ans + 1) + "\n"); } private static char[] modstring(char[] str) { string s = ""; bool b = true; for (int i = 1; i < str.Length; ++i) { if (str[i - 1] != str[i]) b = true; if (b) { s += str[i - 1]; b = false; } } return s.ToCharArray(); } // Driver Code public static void Main() { // Given String string str = "ABCDABCDABCDA"; minOperationNeeded(str.ToCharArray()); }}// This code is contributed by code_hunt. |
Javascript
<script> // JavaScript program for the above approach // Function to count minimum operations // required to make all characters equal // by repeatedly removing subString function minOperationNeeded(str) { // Remove consecutive duplicate // characters from str str = modstring(str); // Stores length of the String var N = str.length; // Stores frequency of each distinct // characters of the String str var res = new Array(256).fill(0); // Iterate over all the characters // of the String str for (var i = 0; i < N; ++i) { // Update frequency of str[i] res[str[i].charCodeAt(0)] += 1; } // Decrementing the frequency // of the String str[0] res[str[0].charCodeAt(0)] -= 1; // Decrementing the frequency // of the String str[N - 1] res[str[N - 1].charCodeAt(0)] -= 1; // Stores the required count(Max Integer value) var ans = 2147483647; // Iterate over all characters // of the String str for (var i = 0; i < N; ++i) { // Update ans ans = Math.min(ans, res[str[i].charCodeAt(0)]); } document.write(ans + 1 + "<br>"); } function modstring(str) { var s = ""; var b = true; for (var i = 1; i < str.length; ++i) { if (str[i - 1] !== str[i]) b = true; if (b) { s += str[i - 1]; b = false; } } return s.split(""); } // Driver Code // Given String var str = "ABCDABCDABCDA"; minOperationNeeded(str.split("")); </script> |
Output:
3
Time Complexity: O(N)
Auxiliary Space: O(256)
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!
