Permutation of a string with maximum number of characters greater than its adjacent characters
Given a string str, the task is to print the maximum count of characters which are greater than both its left and right character in any permutation of the string.
Examples:
Input: str = “abc”
Output: 1
Permutations of the string with the count of maximal character in each string are:
abc – 0
acb – 1 Here a < c > b
bac – 0
bca – 1 Here b < c > a
cab – 0
cba – 0Input: str = “Beginner”
Output: 2
The string will be “egesk”
Observations:
- If the string’ length is less than 3 then the answer will be 0 because no permutation is possible which satisfies the given condition.
- If the length of the given string is greater than or equal to 3 then assume that in the resulting string every other character is maximal character, that is there is exactly one character between any two consecutive maximal characters (otherwise we can remove all but the lowest one and add them to the end of the string).
- Assume for simplicity that this number is odd. Then, ideally, the string can have maximal characters in even positions i.e.at most (n-1)/2, where n is the length of the given string while the rest of the remaining characters in odd positions.
- First arrange all the characters in ascending order, place the first half characters at odd positions, and then fill the remaining even positions with the rest of the characters.
In this way, all the characters in even positions will be those characters from which character at the left and the right position are smaller if there is no frequency of smaller character that is too high, start placing a character from an odd position, continue with the same character to even positions, and eventually reach a position next to the odd position from which we started to place the character. Here if the frequency of some smaller character in the string is too high then the count of maximal character will always be less than (n-1)/2.
Approach:
- Calculate the frequency of each character in the given string.
- Check the character which has the maximum frequency.
- If the maximum frequency element is the smallest element in the given string then mark the flag as 0 otherwise mark the value of flag equal to 1.
- The answer will the minimum of ((n – 1) / 2, n – max_freq – flag).
Below is the implementation of the above approach:
C++
// C++ program to find maximum count // of such characters which are greater // its left and right character in // any permutation of the string #include <bits/stdc++.h> using namespace std; // function to find maximum maximal character in the string int solve( int freq[]) { // to store sum of all frequency int n = 0; // to store maximum frequency int max_freq = 0; // frequency of the smallest element int first; // to check if the smallest // element have maximum frequency or not int flag = 0; // Iterate in the string and count frequency for ( int i = 0; i < 26; i++) { n += freq[i]; // to store frequency of smallest element if (freq[i] != 0 && flag == 0) { first = freq[i]; flag = 1; } // to store maximum frequency if (max_freq < freq[i]) max_freq = freq[i]; } // if sum of frequency of all element if 0 if (n == 0) return 0; // if frequency of smallest character // if largest frequency if (first != max_freq) flag = 1; else flag = 0; return min((n - 1) / 2, n - max_freq - flag); } // Function that counts the frequency of // each element void solve(string s) { // array to store the frequency of each character int freq[26]; // initialize frequency of all character with 0 memset (freq, 0, sizeof (freq)); // loop to calculate frequency of // each character in the given string for ( int i = 0; i < s.length(); i++) { freq[s[i] - 'a' ]++; } cout << solve(freq); } // Driver Code int main() { string s = "Beginner" ; solve(s); return 0; } |
Java
// Java program to find maximum count // of such characters which are greater // its left and right character in // any permutation of the string only three characters class GFG { // function to find maximum maximal character in the string static int solve( int freq[]) { // to store sum of all frequency int n = 0 ; // to store maximum frequency int max_freq = 0 ; // frequency of the smallest element int first = 0 ; // to check if the smallest // element have maximum frequency or not int flag = 0 ; // Iterate in the string and count frequency for ( int i = 0 ; i < 26 ; i++) { n += freq[i]; // to store frequency of smallest element if (freq[i] != 0 && flag == 0 ) { first = freq[i]; flag = 1 ; } // to store maximum frequency if (max_freq < freq[i]) { max_freq = freq[i]; } } // if sum of frequency of all element if 0 if (n == 0 ) { return 0 ; } // if frequency of smallest character // if largest frequency if (first != max_freq) { flag = 1 ; } else { flag = 0 ; } return Math.min((n - 1 ) / 2 , n - max_freq - flag); } // Function that counts the frequency of // each element static void solve(String s) { // array to store the frequency of each character int freq[] = new int [ 26 ]; // loop to calculate frequency of // each character in the given string for ( int i = 0 ; i < s.length(); i++) { freq[s.charAt(i) - 'a' ]++; } System.out.println(solve(freq)); } // Driver Code public static void main(String[] args) { String s = "Beginner" ; solve(s); } } // This code is contributed by 29AjayKumar |
Python3
# Python3 program to find maximum # count of such characters which # are greater its left and right # character in any permutation # of the string # function to find maximum maximal # character in the string def Solve_1(freq): # to store sum of all frequency n = 0 # to store maximum frequency max_freq = 0 # to check if the smallest # element have maximum # frequency or not flag = 0 # Iterate in the string # and count frequency for i in range ( 26 ) : n + = freq[i] # to store frequency of # smallest element if (freq[i] ! = 0 and flag = = 0 ) : first = freq[i] flag = 1 # to store maximum frequency if (max_freq < freq[i]): max_freq = freq[i] # if sum of frequency of # all element if 0 if (n = = 0 ): return 0 # if frequency of smallest character # if largest frequency if (first ! = max_freq): flag = 1 else : flag = 0 return min ((n - 1 ) / / 2 , n - max_freq - flag) # Function that counts the # frequency of each element def solve(s): # array to store the frequency # of each character initialize # frequency of all character with 0 freq = [ 0 ] * 26 # loop to calculate frequency of # each character in the given string for i in range ( len (s)): freq[ ord (s[i]) - ord ( 'a' )] + = 1 print (Solve_1(freq)) # Driver Code if __name__ = = "__main__" : s = "Beginner" solve(s) # This code is contributed # by ChitraNayal |
C#
// C# program to find maximum count // of such characters which are greater // its left and right character in // any permutation of the string only three characters using System; public class GFG{ //JAVA program to find maximum count // of such characters which are greater // its left and right character in // any permutation of the string only three characters // function to find maximum maximal character in the string static int solve( int []freq) { // to store sum of all frequency int n = 0; // to store maximum frequency int max_freq = 0; // frequency of the smallest element int first = 0; // to check if the smallest // element have maximum frequency or not int flag = 0; // Iterate in the string and count frequency for ( int i = 0; i < 26; i++) { n += freq[i]; // to store frequency of smallest element if (freq[i] != 0 && flag == 0) { first = freq[i]; flag = 1; } // to store maximum frequency if (max_freq < freq[i]) { max_freq = freq[i]; } } // if sum of frequency of all element if 0 if (n == 0) { return 0; } // if frequency of smallest character // if largest frequency if (first != max_freq) { flag = 1; } else { flag = 0; } return Math.Min((n - 1) / 2, n - max_freq - flag); } // Function that counts the frequency of // each element static void solve(String s) { // array to store the frequency of each character int []freq = new int [26]; // loop to calculate frequency of // each character in the given string for ( int i = 0; i < s.Length; i++) { freq[s[i] - 'a' ]++; } Console.Write(solve(freq)); } // Driver Code public static void Main() { String s = "Beginner" ; solve(s); } } // This code is contributed by Rajput-JI |
PHP
<?php // PHP program to find maximum count of such // characters which are greater its left and // right character in any permutation // of the string // function to find maximum maximal // character in the string function Solve_1( $freq ) { // to store sum of all frequency $n = 0; // to store maximum frequency $max_freq = 0; // to check if the smallest element // have maximum frequency or not $flag = 0; // Iterate in the string // and count frequency for ( $i = 0; $i < 26; $i ++) { $n += $freq [ $i ]; // to store frequency of // smallest element if ( $freq [ $i ] != 0 and $flag == 0) { $first = $freq [ $i ]; $flag = 1; } // to store maximum frequency if ( $max_freq < $freq [ $i ]) $max_freq = $freq [ $i ]; } // if sum of frequency of // all element if 0 if ( $n == 0) return 0; // if frequency of smallest character // if largest frequency if ( $first != $max_freq ) $flag = 1; else $flag = 0; return min(( $n - 1) / 2, $n - $max_freq - $flag ); } // Function that counts the // frequency of each element function solve( $s ) { // array to store the frequency // of each character initialize // frequency of all character with 0 $freq = array_fill (0, 26, 0); // loop to calculate frequency of // each character in the given string for ( $i = 0; $i < strlen ( $s ); $i ++) $freq [ord( $s [ $i ]) - ord( 'a' )] += 1; print (Solve_1( $freq )); } // Driver Code $s = "Beginner" ; solve( $s ); // This code is contributed // by mits ?> |
Javascript
<script> // Javascript program to find maximum count // of such characters which are greater // its left and right character in // any permutation of the string only three characters // function to find maximum maximal character in the string function solve1(freq) { // to store sum of all frequency let n = 0; // to store maximum frequency let max_freq = 0; // frequency of the smallest element let first = 0; // to check if the smallest // element have maximum frequency or not let flag = 0; // Iterate in the string and count frequency for (let i = 0; i < 26; i++) { n += freq[i]; // to store frequency of smallest element if (freq[i] != 0 && flag == 0) { first = freq[i]; flag = 1; } // to store maximum frequency if (max_freq < freq[i]) { max_freq = freq[i]; } } // if sum of frequency of all element if 0 if (n == 0) { return 0; } // if frequency of smallest character // if largest frequency if (first != max_freq) { flag = 1; } else { flag = 0; } return Math.min(Math.floor((n - 1) / 2), n - max_freq - flag); } // Function that counts the frequency of // each element function solve(s) { // array to store the frequency of each character let freq = new Array(26); for (let i=0;i<26;i++) { freq[i]=0; } // loop to calculate frequency of // each character in the given string for (let i = 0; i < s.length; i++) { freq[s[i].charCodeAt(0) - 'a' .charCodeAt(0)]++; } document.write(solve1(freq)); } // Driver Code let s = "Beginner" ; solve(s); // This code is contributed by avanitrachhadiya2155 </script> |
Output
2
Complexity Analysis:
- Time Complexity: O(n), where n is the size of the given string
- Auxiliary Space: O(26)