Cost to make a string Panagram | Set 2
Given an array cost[] containing the cost of adding each alphabet from (a – z) and a string str consisting of lowercase English alphabets which may or may not be a Panagram. The task is to make the given string a Panagram with the following operations:
- Adding a character in str costs twice the cost associated with that character.
- Removing a character from str will result in gaining the exact cost associated with that character.
Print the cost of making the given string a Panagram, if the gain is more than the cost then print 0.
Examples:
Input: arr[] = {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1},
str = “w3wiki”
Output: 32
Occurrences of the characters are as follow:
g = 2, e = 4, k = 2, s = 2, f = 1, o = 1 and r = 1
The remaining 19 characters from the English alphabets will be added at cost 2 for each i.e. 2 * 19 = 38
And, 1, 3, 1 and 1 occurrences of the characters ‘g’, ‘e’, ‘k’ and ‘s’ respectively can be traded for gain (1 + 3 + 1 + 1) i.e. 6
So, the normalized cost is 38 – 6 = 32Input: arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26},
str = “thequickbrownfoxjumpsoverthelazydog”
Output: 0
The given string is already a Panagram
Approach:
- Store the occurrence for each of the character in an array occurrences[].
- Initialize gain = 0 and start traversing the array occurrences[], for every character ch:
- If ch occurs more than once say x times then x – 1 of its occurrences can be traded for some gain i.e. gain = gain + cost[ch] * (x – 1).
- If ch doesn’t occur in str then it has to be added at twice the cost i.e. gain = gain – (2 * cost[ch]).
- If gain ? 0 then print 0.
- Else print gain * -1 which is the cost of making str a Panagram.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach #include<bits/stdc++.h> using namespace std; // Function to return the cost // to make str a Panagram int costToPanagram(string str, int cost[]) { int i, n = str.length(); int occurrences[26] = {0}; // Count the occurrences of // each lowercase character for (i = 0; i < n; i++) occurrences[str[i] - 'a' ]++; // To store the total gain int gain = 0; for (i = 0; i < 26; i++) { // If some character is missing, // it has to be added at twice the cost if (occurrences[i] == 0) gain -= (2 * cost[i]); // If some character appears more // than once, all of its occurrences // except 1 can be traded for some gain else if (occurrences[i] > 1) gain += (cost[i] * (occurrences[i] - 1)); } // If gain is more than the cost if (gain >= 0) return 0; // Return the total cost if gain < 0 return (gain * -1); } // Driver code int main() { int cost[] = { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 }; string str = "w3wiki" ; cout << costToPanagram(str, cost); } // This code is contributed by // Surendra_Gangwar |
Java
// Java implementation of the approach public class GFG { // Function to return the cost to make str a Panagram static int costToPanagram(String str, int cost[]) { int i, n = str.length(); int occurrences[] = new int [ 26 ]; // Count the occurrences of each lowercase character for (i = 0 ; i < n; i++) occurrences[str.charAt(i) - 'a' ]++; // To store the total gain int gain = 0 ; for (i = 0 ; i < 26 ; i++) { // If some character is missing, it has to be added // at twice the cost if (occurrences[i] == 0 ) gain -= ( 2 * cost[i]); // If some character appears more than once // all of its occurrences except 1 // can be traded for some gain else if (occurrences[i] > 1 ) gain += (cost[i] * (occurrences[i] - 1 )); } // If gain is more than the cost if (gain >= 0 ) return 0 ; // Return the total cost if gain < 0 return (gain * - 1 ); } // Driver code public static void main(String[] args) { int cost[] = { 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 }; String str = "w3wiki" ; System.out.println(costToPanagram(str, cost)); } } |
Python3
# Python3 implementation of the approach # Function to return the cost to # make string a Panagram def costToPanagram(string, cost): n = len (string) occurrences = [ 0 ] * 26 # Count the occurrences of each # lowercase character for i in range (n): occurrences[ ord (string[i]) - ord ( 'a' )] + = 1 # To store the total gain gain = 0 for i in range ( 26 ): # If some character is missing, # it has to be added at twice the cost if occurrences[i] = = 0 : gain - = 2 * cost[i] # If some character appears more than # once all of its occurrences except 1 # can be traded for some gain elif occurrences[i] > 1 : gain + = cost[i] * (occurrences[i] - 1 ) # If gain is more than the cost if gain > = 0 : return 0 # Return the total cost if gain < 0 return gain * - 1 # Driver code if __name__ = = "__main__" : cost = [ 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 ] string = "w3wiki" print (costToPanagram(string, cost)) # This code is contributed # by Rituraj Jain |
C#
// C# implementation of the approach using System; class GFG { // Function to return the cost to make str a Panagram static int costToPanagram( string str, int []cost) { int i, n = str.Length ; int []occurrences = new int [26]; // Count the occurrences of each lowercase character for (i = 0; i < n; i++) occurrences[str[i] - 'a' ]++; // To store the total gain int gain = 0; for (i = 0; i < 26; i++) { // If some character is missing, it has to be added // at twice the cost if (occurrences[i] == 0) gain -= (2 * cost[i]); // If some character appears more than once // all of its occurrences except 1 // can be traded for some gain else if (occurrences[i] > 1) gain += (cost[i] * (occurrences[i] - 1)); } // If gain is more than the cost if (gain >= 0) return 0; // Return the total cost if gain < 0 return (gain * -1); } // Driver code public static void Main() { int []cost = { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 }; string str = "w3wiki" ; Console.WriteLine(costToPanagram(str, cost)); } } // This code is contributed by Ryuga |
Javascript
<script> // Javascript implementation of the approach // Function to return the cost // to make str a Panagram function costToPanagram(str, cost) { var i, n = str.length; var occurrences = Array(26).fill(0); // Count the occurrences of // each lowercase character for (i = 0; i < n; i++) occurrences[str[i].charCodeAt(0) - 'a' .charCodeAt(0)]++; // To store the total gain var gain = 0; for (i = 0; i < 26; i++) { // If some character is missing, // it has to be added at twice the cost if (occurrences[i] == 0) gain -= (2 * cost[i]); // If some character appears more // than once, all of its occurrences // except 1 can be traded for some gain else if (occurrences[i] > 1) gain += (cost[i] * (occurrences[i] - 1)); } // If gain is more than the cost if (gain >= 0) return 0; // Return the total cost if gain < 0 return (gain * -1); } // Driver code var cost = [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]; var str = "w3wiki" ; document.write( costToPanagram(str, cost)); // This code is contributed by importantly. </script> |
32
Time Complexity: O(n), where n is the length of the given string.
Auxiliary Space: O(1)
Contact Us