Maximize palindromic strings of length 3 possible from given count of alphabets
Given an array arr[] of size 26, representing frequencies of character ‘a’ to ‘z’, the task is to find the maximum number of palindromic strings of length 3 that can be generated from the specified count of alphabets.
Examples:
Input: arr[] = {4, 5, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}
Output: 3
Explanation:One of the possible solution is to take two characters of ‘b’ and one character of ‘a’, making string “bab”. Now, 3 ‘a’ and 3 ‘b’ are left from which strings “aaa” and “bbb” can be made. Thus total of 3 palindromic strings can be formed.Input: arr[] = {2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}
Output: 1
Explanation: The only possible palindromic string is “aba”.
Approach: The given problem can be solved based on the following observations:
- The number of strings can be maximized by first making possible strings only of one type of character.
- After that take two characters of one type and one character of the other kind and forming a string.
- If still characters which occur more than 1 exist, then take 3 among such characters and form 2 strings of type “ACA” and “BCB”.
- If again two characters are left which occurs 2 times, then form a string and add one more to answer.
- After this, only characters that occur only once or a character that occurs twice will be left.
Follow the steps below to solve the problem:
- Initialize a variable, res with 0 to store the count of maximum palindromic strings of size 3 that can be formed.
- Initialize a variable, C1, and C2 with 0 to store the count of characters having frequency one and two respectively
- Iterate over the array, arr[] and increment the res by arr[i]/3, set arr[i] to arr[i]%3, and increment C1 by 1 if arr[i]%3 is 1, otherwise, increment C2 by 1 if arr[i]%3 is 2.
- After traversal, increment res by min (C1, C2) and update C1 and C2. Then, increment res by twice of C2/3 and update C2. Lastly, increment res by C2/2.
- Finally, print res as the answer.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to count maximum number // of palindromic string of length 3 void maximum_pallindromic( int arr[]) { // Stores the final count of // palindromic strings int res = 0; int c1 = 0, c2 = 0; // Traverse the array for ( int i = 0; i < 26; i++) { // Increment res by arr[i]/3, // i.e forming string of // only i +'a' character res += arr[i] / 3; // Store remainder arr[i] = arr[i] % 3; // Increment c1 by one, if // current frequency is 1 if (arr[i] == 1) c1++; // Increment c2 by one, if // current frequency is 2 else if (arr[i] == 2) c2++; } // Count palindromic strings of // length 3 having the character // at the ends different from that // present in the middle res += min(c1, c2); int t = min(c1, c2); // Update c1 and c2 c1 -= t; c2 -= t; // Increment res by 2 * c2/3 res += 2 * (c2 / 3); c2 %= 3; res += c2 / 2; // Finally print the result cout << res; } // Driver Code int main() { // Given array int arr[] = { 4, 5, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }; // Function Call maximum_pallindromic(arr); return 0; } |
Java
// Java program for the above approach import java.util.*; class GFG { // Function to count maximum number // of palindromic String of length 3 static void maximum_pallindromic( int arr[]) { // Stores the final count of // palindromic Strings int res = 0 ; int c1 = 0 , c2 = 0 ; // Traverse the array for ( int i = 0 ; i < 26 ; i++) { // Increment res by arr[i]/3, // i.e forming String of // only i +'a' character res += arr[i] / 3 ; // Store remainder arr[i] = arr[i] % 3 ; // Increment c1 by one, if // current frequency is 1 if (arr[i] == 1 ) c1++; // Increment c2 by one, if // current frequency is 2 else if (arr[i] == 2 ) c2++; } // Count palindromic Strings of // length 3 having the character // at the ends different from that // present in the middle res += Math.min(c1, c2); int t = Math.min(c1, c2); // Update c1 and c2 c1 -= t; c2 -= t; // Increment res by 2 * c2/3 res += 2 * (c2 / 3 ); c2 %= 3 ; res += c2 / 2 ; // Finally print the result System.out.print(res); } // Driver Code public static void main(String[] args) { // Given array int arr[] = { 4 , 5 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 }; // Function Call maximum_pallindromic(arr); } } // This code is contributed by aashish1995 |
Python3
# Python3 program for the above approach # Function to count maximum number # of palindromic string of length 3 def maximum_pallindromic(arr): # Stores the final count of # palindromic strings res = 0 c1 = 0 c2 = 0 # Traverse the array for i in range ( 26 ): # Increment res by arr[i]/3, # i.e forming string of # only i +'a' character res + = arr[i] / / 3 # Store remainder arr[i] = arr[i] % 3 # Increment c1 by one, if # current frequency is 1 if (arr[i] = = 1 ): c1 + = 1 # Increment c2 by one, if # current frequency is 2 elif (arr[i] = = 2 ): c2 + = 1 # Count palindromic strings of # length 3 having the character # at the ends different from that # present in the middle res + = min (c1, c2) t = min (c1, c2) # Update c1 and c2 c1 - = t c2 - = t # Increment res by 2 * c2/3 res + = 2 * (c2 / / 3 ) c2 % = 3 res + = c2 / / 2 # Finally print the result print (res) # Driver Code if __name__ = = "__main__" : # Given array arr = [ 4 , 5 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 ] # Function Call maximum_pallindromic(arr) # This code is contributed by chitranayal |
C#
// C# program for the above approach using System; public class GFG { // Function to count maximum number // of palindromic String of length 3 static void maximum_pallindromic( int []arr) { // Stores the readonly count of // palindromic Strings int res = 0; int c1 = 0, c2 = 0; // Traverse the array for ( int i = 0; i < 26; i++) { // Increment res by arr[i]/3, // i.e forming String of // only i +'a' character res += arr[i] / 3; // Store remainder arr[i] = arr[i] % 3; // Increment c1 by one, if // current frequency is 1 if (arr[i] == 1) c1++; // Increment c2 by one, if // current frequency is 2 else if (arr[i] == 2) c2++; } // Count palindromic Strings of // length 3 having the character // at the ends different from that // present in the middle res += Math.Min(c1, c2); int t = Math.Min(c1, c2); // Update c1 and c2 c1 -= t; c2 -= t; // Increment res by 2 * c2/3 res += 2 * (c2 / 3); c2 %= 3; res += c2 / 2; // Finally print the result Console.Write(res); } // Driver Code public static void Main(String[] args) { // Given array int []arr = { 4, 5, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }; // Function Call maximum_pallindromic(arr); } } // This code is contributed by 29AjayKumar |
Javascript
<script> // Javascript program for the above approach // Function to count maximum number // of palindromic string of length 3 function maximum_pallindromic(arr) { // Stores the final count of // palindromic strings var res = 0; var c1 = 0, c2 = 0; // Traverse the array for ( var i = 0; i < 26; i++) { // Increment res by arr[i]/3, // i.e forming string of // only i +'a' character res += parseInt(arr[i] / 3); // Store remainder arr[i] = (arr[i] % 3); // Increment c1 by one, if // current frequency is 1 if (arr[i] == 1) c1++; // Increment c2 by one, if // current frequency is 2 else if (arr[i] == 2) c2++; } // Count palindromic strings of // length 3 having the character // at the ends different from that // present in the middle res += Math.min(c1, c2); var t = Math.min(c1, c2); // Update c1 and c2 c1 -= t; c2 -= t; // Increment res by 2 * c2/3 res += 2 * parseInt(c2 / 3); c2 %= 3; res += parseInt(c2 / 2); // Finally print the result document.write( res); } // Driver Code // Given array var arr = [ 4, 5, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ]; // Function Call maximum_pallindromic(arr); </script> |
3
Time Complexity: O(1)
Auxiliary Space: O(1)
Contact Us