Given a string str that consists of characters and spaces, the task is to find the minimum cost to reduce the number of spaces between characters of the string.
Cost of moving a character for index i to index j is defined as: | i – j |
Examples:
Input: str = ” @ $”
Output: 4
Explanation:
As the characters are at indices [2, 7] (only two), either move the first character to the nearest second character or vice-versa. The cost required is |2-6| = 4 or |6-2| = 4.
Therefore, the minimum cost is 4.Input: str = ” A ”
Output: 0
Explanation:
Since the string consists of only one character, no changes required. Therefore, minimum cost is 0.
Approach: The idea is to move all the characters nearest to the middle of the string so that the overall cost is minimized. Below are the steps:
- Initialize the total cost with 0.
- Transverse the string and count the spaces between the two characters.
- Get both the characters together and add the cost to the total cost.
- Repeat the above steps for all characters.
Below is the implementation of the above approach:
C++
// C++ program to gather characters // of a string in minimum cost #include <bits/stdc++.h>using namespace std;// Function to calculate the // minimum cost int min_cost(string S){ // Stores the minimum cost int cost = 0; // Stores the count of // characters found int F = 0; // Stores the count of // blank spaces found int B = 0; int count = 0; for(char c : S) if(c == ' ') count++; // Stores the count of // total characters int n = S.size() - count; // If the count of characters // is equal to 1 if (n == 1) return cost; // Iterate over the string for(char in : S) { // Consider the previous character // together with current character if (in != ' ') { // If not together already if (B != 0) { // Add the cost to group // them together cost += min(n - F, F) * B; B = 0; } // Increase count of // characters found F += 1; } // Otherwise else { // Increase count of // spaces found B += 1; } } // Return the total // cost obtained return cost;}// Driver Codeint main (){ string S = " @ $"; cout << min_cost(S); return 0;}// This code is contributed by Amit Katiyar |
Java
// Java program to gather characters // of a string in minimum cost import java.util.*;import java.lang.*;class GFG{// Function to calculate the // minimum cost static int min_cost(String S){ // Stores the minimum cost int cost = 0; // Stores the count of // characters found int F = 0; // Stores the count of // blank spaces found int B = 0; int count = 0; for(char c : S.toCharArray()) if(c == ' ') count++; // Stores the count of // total characters int n = S.length() - count; // If the count of characters // is equal to 1 if (n == 1) return cost; // Iterate over the string for(char in : S.toCharArray()) { // Consider the previous character // together with current character if (in != ' ') { // If not together already if (B != 0) { // Add the cost to group // them together cost += Math.min(n - F, F) * B; B = 0; } // Increase count of // characters found F += 1; } // Otherwise else { // Increase count of // spaces found B += 1; } } // Return the total // cost obtained return cost;}// Driver Codepublic static void main (String[] args){ String S = " @ $"; System.out.println(min_cost(S));}}// This code is contributed by offbeat |
Python3
# Python3 program to gather characters# of a string in minimum cost# Function to calculate the# minimum costdef min_cost(S): # Stores the minimum cost cost = 0 # Stores the count of # characters found F = 0 # Stores the count of # blank spaces found B = 0 # Stores the count of # total characters n = len(S)-S.count(' ') # If the count of characters # is equal to 1 if n == 1: return cost # Iterate over the string for char in S: # Consider the previous character # together with current character if char != ' ': # If not together already if B != 0: # Add the cost to group # them together cost += min(n - F, F) * B B = 0 # Increase count of # characters found F += 1 # Otherwise else: # Increase count of # spaces found B += 1 # Return the total # cost obtained return cost# Driver CodeS = " @ $"print(min_cost(S)) |
C#
// C# program to gather characters // of a string in minimum cost using System;class GFG{// Function to calculate the // minimum cost static int min_cost(String S){ // Stores the minimum cost int cost = 0; // Stores the count of // characters found int F = 0; // Stores the count of // blank spaces found int B = 0; int count = 0; foreach(char c in S.ToCharArray()) if(c == ' ') count++; // Stores the count of // total characters int n = S.Length - count; // If the count of characters // is equal to 1 if (n == 1) return cost; // Iterate over the string foreach(char inn in S.ToCharArray()) { // Consider the previous character // together with current character if (inn != ' ') { // If not together already if (B != 0) { // Add the cost to group // them together cost += Math.Min(n - F, F) * B; B = 0; } // Increase count of // characters found F += 1; } // Otherwise else { // Increase count of // spaces found B += 1; } } // Return the total // cost obtained return cost;}// Driver Codepublic static void Main(String[] args){ String S = " @ $"; Console.WriteLine(min_cost(S));}}// This code is contributed by 29AjayKumar |
Javascript
<script>// Javascript program to gather characters// of a string in minimum cost // Function to calculate the// minimum costfunction min_cost(S){ // Stores the minimum cost let cost = 0; // Stores the count of // characters found let F = 0; // Stores the count of // blank spaces found let B = 0; let count = 0; for(let i in S) if(S[i] == ' ') count++; // Stores the count of // total characters let n = S.length - count; // If the count of characters // is equal to 1 if (n == 1) return cost; // Iterate over the string for(let i in S) { // Consider the previous character // together with current character if (S[i] != ' ') { // If not together already if (B != 0) { // Add the cost to group // them together cost += Math.min(n - F, F) * B; B = 0; } // Increase count of // characters found F += 1; } // Otherwise else { // Increase count of // spaces found B += 1; } } // Return the total // cost obtained return cost;}// Driver Code let S = " @ $"; document.write(min_cost(S.split(''))); </script> |
Output:
4
Time Complexity: O(N)
Auxiliary Space: O(1)
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!
