Given a string S consisting of ‘X’, ‘Y’ and ‘Z’ only, the task is to convert S to a string consisting of only a single distinct character by selecting a character and removing substrings that does not contain that character, minimum number of times.
Note: Once a character is chosen, no other character can be used in further operations.
Examples:
Input: S = “XXX”
Output: 0
Explanation: Since the given string already consists of a single distinct character, i.e. X, no removal is required. Therefore, the required count is 0.Input: S = “XYZXYZX”
Output: 2
Explanation:
Selecting the character ‘X’ and removing the substrings “YZ” in two consecutive operations reduces the string to “XXX”, which consists of a single distinct character only.
Approach: The idea is to count occurrences of each character using unordered_map and count the number of removals required for each of them and print the minimum. Follow the steps below to solve the problem:
- Initialize an unordered_map and store the indices of occurrences for each of the characters.
- Iterate over all the characters of the string S and update occurrences of the characters ‘X’, ‘Y’ and ‘Z’ in the map.
- Iterate over the Map and for each character, count the number of removals required for each character.
- After calculating for each character, print the minimum count obtained for any of the characters.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to find minimum removals// required to convert given string// to single distinct characters onlyint minimumOperations(string s, int n){ // Unordered map to store positions // of characters X, Y and Z unordered_map<char, vector<int> > mp; // Update indices of X, Y, Z; for (int i = 0; i < n; i++) { mp[s[i]].push_back(i); } // Stores the count of // minimum removals int ans = INT_MAX; // Traverse the Map for (auto x : mp) { int curr = 0; int prev = 0; bool first = true; // Count the number of removals // required for current character for (int index : (x.second)) { if (first) { if (index > 0) { curr++; } prev = index; first = false; } else { if (index != prev + 1) { curr++; } prev = index; } } if (prev != n - 1) { curr++; } // Update the answer ans = min(ans, curr); } // Print the answer cout << ans;}// Driver Codeint main(){ // Given string string s = "YYXYZYXYZXY"; // Size of string int N = s.length(); // Function call minimumOperations(s, N); return 0;} |
Java
// Java program for the above approachimport java.util.*;class GFG{ // Function to find minimum removals // required to convert given string // to single distinct characters only static void minimumOperations(String s, int n) { // Unordered map to store positions // of characters X, Y and Z HashMap<Character, List<Integer>> mp = new HashMap<>(); // Update indices of X, Y, Z; for(int i = 0; i < n; i++) { if (mp.containsKey(s.charAt(i))) { mp.get(s.charAt(i)).add(i); } else { mp.put(s.charAt(i), new ArrayList<Integer>(Arrays.asList(i))); } } // Stores the count of // minimum removals int ans = Integer.MAX_VALUE; // Traverse the Map for (Map.Entry<Character, List<Integer>> x : mp.entrySet()) { int curr = 0; int prev = 0; boolean first = true; // Count the number of removals // required for current character for(Integer index : (x.getValue())) { if (first) { if (index > 0) { curr++; } prev = index; first = false; } else { if (index != prev + 1) { curr++; } prev = index; } } if (prev != n - 1) { curr++; } // Update the answer ans = Math.min(ans, curr); } // Print the answer System.out.print(ans); } // Driver code public static void main(String[] args) { // Given string String s = "YYXYZYXYZXY"; // Size of string int N = s.length(); // Function call minimumOperations(s, N); }}// This code is contributed by divyeshrabadiya07 |
Python3
# Python3 program for the above approachimport sys;INT_MAX = sys.maxsize;# Function to find minimum removals# required to convert given string# to single distinct characters onlydef minimumOperations(s, n) : # Unordered map to store positions # of characters X, Y and Z mp = {}; # Update indices of X, Y, Z; for i in range(n) : if s[i] in mp : mp[s[i]].append(i); else : mp[s[i]] = [i]; # Stores the count of # minimum removals ans = INT_MAX; # Traverse the Map for x in mp : curr = 0; prev = 0; first = True; # Count the number of removals # required for current character for index in mp[x] : if (first) : if (index > 0) : curr += 1; prev = index; first = False; else : if (index != prev + 1) : curr += 1; prev = index; if (prev != n - 1) : curr += 1; # Update the answer ans = min(ans, curr); # Print the answer print(ans);# Driver Codeif __name__ == "__main__" : # Given string s = "YYXYZYXYZXY"; # Size of string N = len(s); # Function call minimumOperations(s, N); # This code is contributed by AnkThon |
C#
// C# program for the above approachusing System;using System.Collections.Generic; class GFG{ // Function to find minimum removals// required to convert given string// to single distinct characters onlystatic void minimumOperations(string s, int n){ // Unordered map to store positions // of characters X, Y and Z Dictionary<char, List<int>> mp = new Dictionary<char, List<int>>(); // Update indices of X, Y, Z; for(int i = 0; i < n; i++) { if (mp.ContainsKey(s[i])) { mp[s[i]].Add(i); } else { mp[s[i]] = new List<int>(); mp[s[i]].Add(i); } } // Stores the count of // minimum removals int ans = Int32.MaxValue; // Traverse the Map foreach(KeyValuePair<char, List<int>> x in mp) { int curr = 0; int prev = 0; bool first = true; // Count the number of removals // required for current character foreach(int index in (x.Value)) { if (first) { if (index > 0) { curr++; } prev = index; first = false; } else { if (index != prev + 1) { curr++; } prev = index; } } if (prev != n - 1) { curr++; } // Update the answer ans = Math.Min(ans, curr); } // Print the answer Console.Write(ans);}// Driver Codestatic void Main(){ // Given string string s = "YYXYZYXYZXY"; // Size of string int N = s.Length; // Function call minimumOperations(s, N);}}// This code is contributed by divyesh072019 |
Javascript
<script> // JavaScript program for the above approach // Function to find minimum removals // required to convert given string // to single distinct characters only function minimumOperations(s, n) { // Unordered map to store positions // of characters X, Y and Z var mp = {}; // Update indices of X, Y, Z; for (var i = 0; i < n; i++) { if (mp.hasOwnProperty(s[i])) { mp[s[i]].push(i); } else { mp[s[i]] = []; mp[s[i]].push(i); } } // Stores the count of // minimum removals var ans = 2147483647; // Traverse the Map for (const [key, value] of Object.entries(mp)) { var curr = 0; var prev = 0; var first = true; // Count the number of removals // required for current character for (const index of value) { if (first) { if (index > 0) { curr++; } prev = index; first = false; } else { if (index !== prev + 1) { curr++; } prev = index; } } if (prev !== n - 1) { curr++; } // Update the answer ans = Math.min(ans, curr); } // Print the answer document.write(ans); } // Driver Code // Given string var s = "YYXYZYXYZXY"; // Size of string var N = s.length; // Function call minimumOperations(s, N); // This code is contributed by rdtank. </script> |
Output:
3
Time Complexity: O(N)
Auxiliary Space: O(N)
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!
