Given a string S of length N consisting of lowercase alphabets, the task is to count the minimum number of characters that need to be replaced to make the given string S special.
A string S is special if and only if for all possible pairs (S[i], S[j]) ( 1-based indexing ) where 1 ? i ? N/2 and N / 2 + 1 ? j ? N, one of the following condition must be true:
- S[i] < S[j]: For indices (i, j), each character in the left half (S[i]) is less than each character in the right half (S[j]).
- S[i] > S[j]: For index (i, j), each character in left half (S[i]) is greater than each character in the right half (S[j]).
- S[i] = S[j]: For index (i, j), each character in left half (S[i]) is equal to each character in the right half (S[j]).
Examples:
Input: S = “aababc“
Output: 2
Explanation:
The left and right part of the string are Left= “aab”, Right=”abc”
Operation 1: Change s[4] ? d
Operation 2: Change s[5] ? d
After applying the above changes, the resultant string is “aabddc” which satisfy all the conditions for special string.Input: S = “aabaab”
Output: 2
Explanation:
The left and right part of the string are Left=”aab” Right=”aab”
Operation 1: Change s[3] ? a
Operation 2: Change s[6] ? a
After applying the above changes, the resultant string is “aaaaaa” which satisfy all the conditions for special string.
Approach: The idea is to observe that there is only 26 alphabets number of changes for s[i]==s[j] can be done using counting the frequency of characters. Follow the steps below to solve the above problem:
- Store the frequency of characters of left and right half are stored in the array left[] and right[] respectively.
- Initialize a variable count to keeps track of the minimum number of changes to be made.
- Traverse over the range [0, 26] using variable d and change the characters as per the below cases:
- For s[i] equals s[j]: Make all characters equal to a character c, then the value of count is (N – left – right).
- For s[i] less than s[j]:
- Initially, with the maximum number of changes, make on the left side, let changes be N/2.
- Subtract all the characters on the left side which are ? d to find the remaining characters to be changed.
- Add all characters on the right side which are equal to d to change those characters that are greater than d as change -= left and change += right.
- For s[i] greater than s[j]:
- Initially, with the maximum number of changes, make on the right side, let change be N/2.
- Subtract all the characters on the right side which are ?d to find the remaining characters to be changed.
- Add all characters on the left side which are equal to d to change those characters to > d. (s[i]<s[j]) as change += left and change -= right.
- The minimum of all the count in the above cases is the required result.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include<bits/stdc++.h>using namespace std;// Function that finds the minimum// count of steps required to make// the string specialint minChange(string s, int n){ // Stores the frequency of the // left & right half of string int L[26] = {0}; int R[26] = {0}; // Find frequency of left half for(int i = 0; i < n / 2; i++) { char ch = s[i]; L[ch - 'a']++; } // Find frequency of left half for(int i = n / 2; i < n; i++) { char ch = s[i]; R[ch - 'a']++; } int count = n; // Make all characters equal // to character c for(char ch = 'a'; ch <= 'z'; ch++) { count = min(count, n - L[ch - 'a'] - R[ch - 'a']); } // Case 1: For s[i] < s[j] int change = n / 2; for(int d = 0; d + 1 < 26; d++) { // Subtract all the characters // on left side that are <=d change -= L[d]; // Adding all characters on the // right side that same as d change += R[d]; // Find minimum value of count count = min(count, change); } // Similarly for Case 2: s[i] > s[j] change = n / 2; for(int d = 0; d + 1 < 26; d++) { change -= R[d]; change += L[d]; count = min(change, count); } // Return the minimum changes return count;}// Driver Codeint main(){ // Given string S string S = "aababc"; int N = S.length(); // Function Call cout << minChange(S, N) << "\n";}// This code is contributed by sallagondaavinashreddy7 |
Java
// Java program for the above approachimport java.io.*;import java.util.*;class Main { // Function that finds the minimum // count of steps required to make // the string special public static int minChange(String s, int n) { // Stores the frequency of the // left & right half of string int L[] = new int[26]; int R[] = new int[26]; // Find frequency of left half for (int i = 0; i < n / 2; i++) { char ch = s.charAt(i); L[ch - 'a']++; } // Find frequency of left half for (int i = n / 2; i < n; i++) { char ch = s.charAt(i); R[ch - 'a']++; } int count = n; // Make all characters equal // to character c for (char ch = 'a'; ch <= 'z'; ch++) { count = Math.min( count, n - L[ch - 'a'] - R[ch - 'a']); } // Case 1: For s[i] < s[j] int change = n / 2; for (int d = 0; d + 1 < 26; d++) { // Subtract all the characters // on left side that are <=d change -= L[d]; // Adding all characters on the // right side that same as d change += R[d]; // Find minimum value of count count = Math.min(count, change); } // Similarly for Case 2: s[i] > s[j] change = n / 2; for (int d = 0; d + 1 < 26; d++) { change -= R[d]; change += L[d]; count = Math.min(change, count); } // Return the minimum changes return count; } // Driver Code public static void main(String[] args) { // Given string S String S = "aababc"; int N = S.length(); // Function Call System.out.println(minChange(S, N)); }} |
Python3
# Python3 program for the # above approach# Function that finds the minimum# count of steps required to make# the string specialdef minChange (s, n): # Stores the frequency of the # left & right half of string L = [0] * 26; R = [0] * 26; # Find frequency of left half for i in range(0, n // 2): ch = s[i]; L[ord(ch) - ord('a')] += 1; # Find frequency of left half for i in range(n // 2, n): ch = s[i]; R[ord(ch) - ord('a')] += 1; count = n; # Make all characters equal # to character c for ch in range(ord('a'), ord('z')): count = min(count, n - L[ch - ord('a')] - R[ch - ord('a')]); # Case 1: For s[i] < s[j] change = n / 2; for d in range(0, 25): # Subtract all the characters # on left side that are <=d change -= L[d]; # Adding all characters on the # right side that same as d change += R[d]; # Find minimum value of count count = min(count, change); # Similarly for Case 2: s[i] > s[j] change = n / 2; for d in range(0, 25): change -= R[d]; change += L[d]; count = min(change, count); # Return the minimum changes return int(count);# Driver Codeif __name__ == '__main__': # Given string S S = "aababc"; N = len(S); # Function Call print(minChange(S, N));# This code is contributed by shikhasingrajput |
C#
// C# program for the above approachusing System;class GFG{ // Function that finds the minimum// count of steps required to make// the string specialpublic static int minChange(String s, int n){ // Stores the frequency of the // left & right half of string int []L = new int[26]; int []R = new int[26]; // Find frequency of left half for(int i = 0; i < n / 2; i++) { char ch = s[i]; L[ch - 'a']++; } // Find frequency of left half for(int i = n / 2; i < n; i++) { char ch = s[i]; R[ch - 'a']++; } int count = n; // Make all characters equal // to character c for(char ch = 'a'; ch <= 'z'; ch++) { count = Math.Min(count, n - L[ch - 'a'] - R[ch - 'a']); } // Case 1: For s[i] < s[j] int change = n / 2; for(int d = 0; d + 1 < 26; d++) { // Subtract all the characters // on left side that are <=d change -= L[d]; // Adding all characters on the // right side that same as d change += R[d]; // Find minimum value of count count = Math.Min(count, change); } // Similarly for Case 2: s[i] > s[j] change = n / 2; for(int d = 0; d + 1 < 26; d++) { change -= R[d]; change += L[d]; count = Math.Min(change, count); } // Return the minimum changes return count;}// Driver Codepublic static void Main(String[] args){ // Given string S String S = "aababc"; int N = S.Length; // Function Call Console.WriteLine(minChange(S, N));}}// This code is contributed by Amit Katiyar |
Javascript
<script> // JavaScript program for the above approach // Function that finds the minimum // count of steps required to make // the string special function minChange(s, n) { // Stores the frequency of the // left & right half of string var L = new Array(26).fill(0); var R = new Array(26).fill(0); // Find frequency of left half for (var i = 0; i < n / 2; i++) { var ch = s[i].charCodeAt(0); L[ch - "a".charCodeAt(0)]++; } // Find frequency of left half for (var i = n / 2; i < n; i++) { var ch = s[i].charCodeAt(0); R[ch - "a".charCodeAt(0)]++; } var count = n; // Make all characters equal // to character c for (var ch = "a".charCodeAt(0); ch <= "z".charCodeAt(0); ch++) { count = Math.min( count, n - L[ch - "a".charCodeAt(0)] - R[ch - "a".charCodeAt(0)] ); } // Case 1: For s[i] < s[j] var change = parseInt(n / 2); for (var d = 0; d + 1 < 26; d++) { // Subtract all the characters // on left side that are <=d change -= L[d]; // Adding all characters on the // right side that same as d change += R[d]; // Find minimum value of count count = Math.min(count, change); } // Similarly for Case 2: s[i] > s[j] change = n / 2; for (var d = 0; d + 1 < 26; d++) { change -= R[d]; change += L[d]; count = Math.min(change, count); } // Return the minimum changes return count; } // Driver Code // Given string S var S = "aababc"; var N = S.length; // Function Call document.write(minChange(S, N)); </script> |
Output:
2
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!
