Given a string S, the task is to calculate the minimum cost to sort the string in increasing order of their frequencies by swapping a block of repeated characters with another block of different repeated characters. The cost of each operation is the absolute difference of the two blocks.
Examples:
Input: S = “aabbcccdeffffggghhhhhii”
Output: 5
Explanation:
- Swap ‘d’ with ‘aa’. The Cost of this Operation is 1
- Swap ‘e’ with ‘bb’. The Cost of this Operation is 1
- Swap ‘ii’ with ‘ccc’. The Cost of this Operation is cost is 1
- Swap ‘ccc’ with ‘ffff’. The Cost of this Operation is 1
- Swap ‘ffff’ with ‘hhhhh’. The Cost of this Operation is 1
Input : S = “aaaa”
Output : 0
Approach:
Follow the steps below to solve the problem:
- Store the frequency of each character present in the String.
- Sort the frequencies.
- Calculate the difference between each frequency in the sorted and original sequence.
- Half of the total sum of all the differences is the required answer. This is because, for each swap, the difference is calculated twice in the above step.
Below is the implementation of the above approach:
C++
// C++ program to implement // above approach#include <bits/stdc++.h>using namespace std; int sortString(string S) { vector<int> sorted, original; bool insert = false; // For a single character if (S.length() == 1) { cout << 0 << endl; } // Stores count of repetitions // of a character int curr = 1; for(int i = 0; i < (S.length() - 1); i++) { // If repeating character if (S[i] == S[i + 1]) { curr += 1; insert = false; } // Otherwise else { // Store frequency sorted.push_back(curr); original.push_back(curr); // Reset count curr = 1; insert = true; } } // Insert the last character block if ((S[(S.length() - 1)] != S[(S.length() - 2)]) || insert == false) { sorted.push_back(curr); original.push_back(curr); } // Sort the frequencies sort(sorted.begin(), sorted.end()); // Stores the minimum cost of all operations int t_cost = 0; for(int i = 0; i < sorted.size(); i++) { // Store the absolute difference of // i-th frequencies of ordered and // unordered sequences t_cost += abs(sorted[i] - original[i]); } // Return the minimum cost return (t_cost / 2); } // Driver Code int main() { string S = "aabbcccdeffffggghhhhhii"; cout << sortString(S); return 0; } |
Java
// Java program to implement // above approachimport java.util.*;class GFG{public static int sortString(String S) { Vector<Integer> sorted = new Vector<Integer>(); Vector<Integer> original = new Vector<Integer>(); boolean insert = false; // For a single character if (S.length() == 1) { System.out.println(0); } // Stores count of repetitions // of a character int curr = 1; for(int i = 0; i < (S.length() - 1); i++) { // If repeating character if (S.charAt(i) == S.charAt(i + 1)) { curr += 1; insert = false; } // Otherwise else { // Store frequency sorted.add(curr); original.add(curr); // Reset count curr = 1; insert = true; } } // Insert the last character block if ((S.charAt(S.length() - 1) != S.charAt(S.length() - 2)) || insert == false) { sorted.add(curr); original.add(curr); } // Sort the frequencies Collections.sort(sorted); // Stores the minimum cost of all operations int t_cost = 0; for(int i = 0; i < sorted.size(); i++) { // Store the absolute difference of // i-th frequencies of ordered and // unordered sequences t_cost += Math.abs(sorted.get(i) - original.get(i)); } // Return the minimum cost return (t_cost / 2); } // Driver codepublic static void main(String[] args){ String S = "aabbcccdeffffggghhhhhii"; System.out.print(sortString(S));}} // This code is contributed by divyeshrabadiya07 |
Python3
# Python3 program to implement# the above approachdef sortString(S): sorted1 = [] original = [] insert = False # For a single character if (len(S) == 1): print(0) # Stores count of repetitions # of a character curr = 1 for i in range(len(S) - 1): # If repeating character if (S[i] == S[i + 1]): curr += 1 insert = False # Otherwise else: # Store frequency sorted1.append(curr) original.append(curr) # Reset count curr = 1 insert = True # Insert the last character block if ((S[(len(S) - 1)] != S[(len(S) - 2)]) or insert == False): sorted1.append(curr) original.append(curr) # Sort the frequencies sorted1.sort() # Stores the minimum cost of all operations t_cost = 0 for i in range(len(sorted1)): # Store the absolute difference of # i-th frequencies of ordered and # unordered sequences t_cost += abs(sorted1[i] - original[i]) # Return the minimum cost return (t_cost // 2)# Driver Codeif __name__ == "__main__": S = "aabbcccdeffffggghhhhhii" print(sortString(S))# This code is contributed by Chitranayal |
C#
// C# program to implement // above approachusing System;using System.Collections.Generic;class GFG{ public static int sortString(string S) { List<int> sorted = new List<int>(); List<int> original = new List<int>(); bool insert = false; // For a single character if (S.Length == 1) { Console.WriteLine(0); } // Stores count of repetitions // of a character int curr = 1; for(int i = 0; i < (S.Length - 1); i++) { // If repeating character if (S[i] == S[i + 1]) { curr += 1; insert = false; } // Otherwise else { // Store frequency sorted.Add(curr); original.Add(curr); // Reset count curr = 1; insert = true; } } // Insert the last character block if ((S[S.Length - 1] != S[S.Length - 2]) || insert == false) { sorted.Add(curr); original.Add(curr); } // Sort the frequencies sorted.Sort(); // Stores the minimum cost of all operations int t_cost = 0; for(int i = 0; i < sorted.Count; i++) { // Store the absolute difference of // i-th frequencies of ordered and // unordered sequences t_cost += Math.Abs(sorted[i] - original[i]); } // Return the minimum cost return (t_cost / 2); }// Driver Code static void Main() { string S = "aabbcccdeffffggghhhhhii"; Console.Write(sortString(S));}}// This code is contributed by divyesh072019 |
Javascript
<script> // Javascript program to implement above approach function sortString(S) { let sorted = []; let original = []; let insert = false; // For a single character if (S.length == 1) { document.write(0 + "</br>"); } // Stores count of repetitions // of a character let curr = 1; for(let i = 0; i < (S.length - 1); i++) { // If repeating character if (S[i] == S[i + 1]) { curr += 1; insert = false; } // Otherwise else { // Store frequency sorted.push(curr); original.push(curr); // Reset count curr = 1; insert = true; } } // Insert the last character block if ((S[S.length - 1] != S[S.length - 2]) || insert == false) { sorted.push(curr); original.push(curr); } // Sort the frequencies sorted.sort(function(a, b){return a - b}); // Stores the minimum cost of all operations let t_cost = 0; for(let i = 0; i < sorted.length; i++) { // Store the absolute difference of // i-th frequencies of ordered and // unordered sequences t_cost += Math.abs(sorted[i] - original[i]); } // Return the minimum cost return parseInt(t_cost / 2, 10); } let S = "aabbcccdeffffggghhhhhii"; document.write(sortString(S));</script> |
Output:
5
Time Complexity: O(NlogN)
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!
