Given string str consisting of lower case alphabets only and an integer K. The task is to find the minimum cost to modify the string such that the ASCII value difference between any two characters of the given string is less than equal to K.
The following operations can be performed on the string:
- Increasing a character: For example, when you increase ‘a’ by 1 it becomes ‘b’. Similarly, if you increase ‘z’ by 1 it becomes ‘a’. The increment is done in a cyclic manner.
- Decreasing a character: For example, when you decrease ‘a’ by 1 it becomes ‘z’. Similarly, if you decrease ‘z’ by 1 it becomes ‘y’. Decrement is done in a cyclic manner.
Examples:
Input: str = “abcd”, K = 1
Output: 2
Change ‘a’ to ‘b’ with cost 1 and ‘d’ to ‘c’ again at cost 1.
Total cost = 1 + 1 = 2.
The modified string will be “bbcc”Input: str = “abcdefghi”, K = 2
Output: 12
Approach: The idea is to maintain a hash table for all the characters of the string to reduce time complexity instead of taking one character at a time. We need to check all the windows containing k contiguous characters and find the minimum cost among all the windows for modifying all the characters of the string.
The cost of modification of a character falls under the following categories:
- Case 1: If the characters are within the window, they will not incur any cost for modifying them.
- Case 2: If the window is in between the characters a-z and the character is on the left side of the window.
- If we increase the character which will incur a cost of d1 or if we decrease the character which will incur a cost of d2+d3, we find a minimum of d1 and d2+d3.
If the window is in between the characters a-z and the character is on the right side of the window.
- If we decrease the character which will incur a cost of d1 or if we increase the character which will incur a cost of d2+d3, we find a minimum of d1 and d2+d3.
- Case 3: If the window is a sub-window of characters ending at z and starting from a and if the character is outside the window.
- If we increase the character, it will incur a cost of d1 and if we decrease the character it will incur a cost of d2, we find a minimum between d1 and d2.
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 minimum costint minCost(string str, int K){ int n = str.length(); // Initialize result int res = 999999999, count = 0, a, b; // To store the frequency of characters // of the string int cnt[27]; // Initialize array with 0 memset(cnt, 0, sizeof(cnt)); // Update the frequencies of the // characters of the string for (int i = 0; i < n; i++) cnt[str[i] - 'a' + 1]++; // Loop to check all windows from a-z // where window size is K for (int i = 1; i < (26 - K + 1); i++) { // Starting index of window a = i; // Ending index of window b = i + K; count = 0; for (int j = 1; j <= 26; j++) { // Check if the string contains character if (cnt[j] > 0) { // Check if the character is on left side of window // find the cost of modification for character // add value to count // calculate nearest distance of modification if (j >= a && j >= b) count = count + (min(j - b, 25 - j + a + 1)) * cnt[j]; // Check if the character is on right side of window // find the cost of modification for character // add value to count // calculate nearest distance of modification else if (j <= a && j <= b) count = count + (min(a - j, 25 + j - b + 1)) * cnt[j]; } } // Find the minimum of all costs // for modifying the string res = min(res, count); } // Loop to check all windows // Here window contains characters // before z and after z of window size K for (int i = 26 - K + 1; i <= 26; i++) { // Starting index of window a = i; // Ending index of window b = (i + K) % 26; count = 0; for (int j = 1; j <= 26; j++) { // Check if the string contains character if (cnt[j] > 0) { // If characters are outside window // find the cost for modifying character // add value to count if (j >= b and j <= a) count = count + (min(j - b, a - j)) * cnt[j]; } } // Find the minimum of all costs // for modifying the string res = min(res, count); } return res;}// Driver codeint main(){ string str = "abcdefghi"; int K = 2; cout << minCost(str, K); return 0;} |
Java
// Java program to implement// the above approachimport java.util.Arrays;class GFG{// Function to return the minimum coststatic int minCost(String str, int K){ int n = str.length(); // Initialize result int res = 999999999, count = 0, a, b; // To store the frequency of characters // of the string int cnt[] = new int[27]; // Initialize array with 0 Arrays.fill(cnt, 0); // Update the frequencies of the // characters of the string for (int i = 0; i < n; i++) cnt[str.charAt(i) - 'a' + 1]++; // Loop to check all windows from a-z // where window size is K for (int i = 1; i < (26 - K + 1); i++) { // Starting index of window a = i; // Ending index of window b = i + K; count = 0; for (int j = 1; j <= 26; j++) { // Check if the string contains character if (cnt[j] > 0) { // Check if the character is on left side of window // find the cost of modification for character // add value to count // calculate nearest distance of modification if (j >= a && j >= b) count = count + (Math.min(j - b, 25 - j + a + 1)) * cnt[j]; // Check if the character is on right side of window // find the cost of modification for character // add value to count // calculate nearest distance of modification else if (j <= a && j <= b) count = count + (Math.min(a - j, 25 + j - b + 1)) * cnt[j]; } } // Find the minimum of all costs // for modifying the string res = Math.min(res, count); } // Loop to check all windows // Here window contains characters // before z and after z of window size K for (int i = 26 - K + 1; i <= 26; i++) { // Starting index of window a = i; // Ending index of window b = (i + K) % 26; count = 0; for (int j = 1; j <= 26; j++) { // Check if the string contains character if (cnt[j] > 0) { // If characters are outside window // find the cost for modifying character // add value to count if (j >= b && j <= a) count = count + (Math.min(j - b, a - j)) * cnt[j]; } } // Find the minimum of all costs // for modifying the string res = Math.min(res, count); } return res;}// Driver codepublic static void main(String[] args){ String str = "abcdefghi"; int K = 2; System.out.println(minCost(str, K));}}/* This code contributed by PrinciRaj1992 */ |
Python3
# Python 3 implementation of the approach# Function to return the minimum costdef minCost(str1, K): n = len(str1) # Initialize result res = 999999999 count = 0 # To store the frequency of characters # of the string cnt = [0 for i in range(27)] # Update the frequencies of the # characters of the string for i in range(n): cnt[ord(str1[i]) - ord('a') + 1] += 1 # Loop to check all windows from a-z # where window size is K for i in range(1, 26 - K + 1, 1): # Starting index of window a = i # Ending index of window b = i + K count = 0 for j in range(1, 27, 1): # Check if the string contains character if (cnt[j] > 0): # Check if the character is on left side of window # find the cost of modification for character # add value to count # calculate nearest distance of modification if (j >= a and j >= b): count = count + (min(j - b, 25 - j + a + 1)) * cnt[j] # Check if the character is on right side of window # find the cost of modification for character # add value to count # calculate nearest distance of modification elif (j <= a and j <= b): count = count + (min(a - j, 25 + j - b + 1)) * cnt[j] # Find the minimum of all costs # for modifying the string res = min(res, count) # Loop to check all windows # Here window contains characters # before z and after z of window size K for i in range(26 - K + 1, 27, 1): # Starting index of window a = i # Ending index of window b = (i + K) % 26 count = 0 for j in range(1, 27, 1): # Check if the string contains character if (cnt[j] > 0): # If characters are outside window # find the cost for modifying character # add value to count if (j >= b and j <= a): count = count + (min(j - b, a - j)) * cnt[j] # Find the minimum of all costs # for modifying the string res = min(res, count) return res# Driver codeif __name__ == '__main__': str1 = "abcdefghi" K = 2 print(minCost(str1, K))# This code is contributed by# Surendra_Gangwar |
C#
// C# program to implement// the above approachusing System;class GFG{// Function to return the minimum coststatic int minCost(String str, int K){ int n = str.Length; // Initialize result int res = 999999999, count = 0, a, b; // To store the frequency of characters // of the string int []cnt = new int[27]; // Update the frequencies of the // characters of the string for (int i = 0; i < n; i++) cnt[str[i] - 'a' + 1]++; // Loop to check all windows from a-z // where window size is K for (int i = 1; i < (26 - K + 1); i++) { // Starting index of window a = i; // Ending index of window b = i + K; count = 0; for (int j = 1; j <= 26; j++) { // Check if the string contains character if (cnt[j] > 0) { // Check if the character is on left side of window // find the cost of modification for character // add value to count // calculate nearest distance of modification if (j >= a && j >= b) count = count + (Math.Min(j - b, 25 - j + a + 1)) * cnt[j]; // Check if the character is on right side of window // find the cost of modification for character // add value to count // calculate nearest distance of modification else if (j <= a && j <= b) count = count + (Math.Min(a - j, 25 + j - b + 1)) * cnt[j]; } } // Find the minimum of all costs // for modifying the string res = Math.Min(res, count); } // Loop to check all windows // Here window contains characters // before z and after z of window size K for (int i = 26 - K + 1; i <= 26; i++) { // Starting index of window a = i; // Ending index of window b = (i + K) % 26; count = 0; for (int j = 1; j <= 26; j++) { // Check if the string contains character if (cnt[j] > 0) { // If characters are outside window // find the cost for modifying character // add value to count if (j >= b && j <= a) count = count + (Math.Min(j - b, a - j)) * cnt[j]; } } // Find the minimum of all costs // for modifying the string res = Math.Min(res, count); } return res;}// Driver codepublic static void Main(String[] args){ String str = "abcdefghi"; int K = 2; Console.WriteLine(minCost(str, K));}}// This code has been contributed by 29AjayKumar |
PHP
<?php// PHP implementation of the approach // Function to return the minimum cost function minCost($str, $K) { $n = strlen($str); // Initialize result $res = 999999999; $count = 0; // To store the frequency of characters // of the string // Initialize array with 0 $cnt = array_fill(0, 27, 0); // Update the frequencies of the // characters of the string for ($i = 0; $i < $n; $i++) $cnt[ord($str[$i]) - ord('a') + 1]++; // Loop to check all windows from a-z // where window size is K for ($i = 1; $i < (26 - $K + 1); $i++) { // Starting index of window $a = $i; // Ending index of window $b = $i + $K; $count = 0; for ($j = 1; $j <= 26; $j++) { // Check if the string contains character if ($cnt[$j] > 0) { // Check if the character is on left side of window // find the cost of modification for character // add value to count // calculate nearest distance of modification if ($j >= $a && $j >= $b) $count = $count + (min($j - $b, 25 - $j + $a + 1)) * $cnt[$j]; // Check if the character is on right side of window // find the cost of modification for character // add value to count // calculate nearest distance of modification else if ($j <= $a && $j <=$b) $count = $count + (min($a - $j, 25 + $j - $b + 1)) * $cnt[$j]; } } // Find the minimum of all costs // for modifying the string $res = min($res, $count); } // Loop to check all windows // Here window contains characters // before z and after z of window size K for ($i = 26 - $K + 1; $i <= 26; $i++) { // Starting index of window $a = $i; // Ending index of window $b = ($i + $K) % 26; $count = 0; for ($j = 1; $j <= 26; $j++) { // Check if the string contains character if ($cnt[$j] > 0) { // If characters are outside window // find the cost for modifying character // add value to count if ($j >= $b and $j <= $a) $count = $count + (min($j - $b,$a - $j)) * $cnt[$j]; } } // Find the minimum of all costs // for modifying the string $res = min($res, $count); } return $res; } // Driver code $str = "abcdefghi"; $K = 2; echo minCost($str, $K); // This code is contributed by Ryuga?> |
Javascript
<script>// Javascript implementation of the approach// Function to return the minimum costfunction minCost(str, K){ var n = str.length; // Initialize result var res = 999999999, count = 0, a, b; // To store the frequency of characters // of the string var cnt = Array(27).fill(0); // Update the frequencies of the // characters of the string for (var i = 0; i < n; i++) cnt[str[i].charCodeAt(0) - 97 + 1]++; // Loop to check all windows from a-z // where window size is K for (var i = 1; i < (26 - K + 1); i++) { // Starting index of window a = i; // Ending index of window b = i + K; count = 0; for (var j = 1; j <= 26; j++) { // Check if the string contains character if (cnt[j] > 0) { // Check if the character is on left side of window // find the cost of modification for character // add value to count // calculate nearest distance of modification if (j >= a && j >= b) count = count + (Math.min(j - b, 25 - j + a + 1)) * cnt[j]; // Check if the character is on right side of window // find the cost of modification for character // add value to count // calculate nearest distance of modification else if (j <= a && j <= b) count = count + (Math.min(a - j, 25 + j - b + 1)) * cnt[j]; } } // Find the minimum of all costs // for modifying the string res = Math.min(res, count); } // Loop to check all windows // Here window contains characters // before z and after z of window size K for (var i = 26 - K + 1; i <= 26; i++) { // Starting index of window a = i; // Ending index of window b = (i + K) % 26; count = 0; for (var j = 1; j <= 26; j++) { // Check if the string contains character if (cnt[j] > 0) { // If characters are outside window // find the cost for modifying character // add value to count if (j >= b && j <= a) count = count + (Math.min(j - b, a - j)) * cnt[j]; } } // Find the minimum of all costs // for modifying the string res = Math.min(res, count); } return res;}// Driver codevar str = "abcdefghi";var K = 2;document.write( minCost(str, K));</script> |
Output:
12
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!
