Horje
Count of 3 sized Strings of all same or different characters using total X 0s, Y 1s and Z 2s

Given three integers X, Y and Z denoting the frequencies of three different characters ‘0‘, ‘1‘, and ‘2’ respectively. the task is to find the maximum number of valid strings of length three that can be formed using the given frequencies such that in each string all the three characters are same or all are different.

Examples:

Input: X = 3, Y = 5, Z = 5
Output: 4
Explanation: Valid strings that can be obtained from the given frequencies: “102”, “012”, “111”, “222”.
Number of strings = 4.

Input: X = 8, Y = 8, Z = 9
Output: 8

 

Approach: The given problem can be solved by the following observations:

  • If there are no such strings that contain all 3 different characters then the answer will always be (X/3 + Y/3 + Z/3).
  • There always exists an optimal solution with less than 3 strings containing all the different characters. Because 3 such strings which contain all the 3 different characters can be changed to (1 all ‘0’ character string + 1 all ‘1’ character string + 1 all ‘2’ character string).

Below is the implementation of the above approach:

C++

// C++ code to implement the approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the maximum valid
// strings that can be formed from
// the given frequencies
int maxValidStrings(int X, int Y, int Z)
{
    // Variable to store the answer
    int ans = 0;
    for (int i = 0; i < 3; i++) {
 
        // If i is greater than any of
        // the frequencies then continue
        if (i > X || i > Y || i > Z) {
            continue;
        }
 
        // Store the remaining characters left
        int xRemain = X - i;
        int yRemain = Y - i;
        int zRemain = Z - i;
 
        // Store the maximum one
        ans = max(ans, i + (xRemain / 3)
                           + (yRemain / 3)
                           + (zRemain / 3));
    }
 
    // Return ans
    return ans;
}
 
// Driver Code
int main()
{
    int X = 8, Y = 8, Z = 9;
 
    // Function call
    cout << maxValidStrings(X, Y, Z);
    return 0;
}

Java

// JAVA code to implement the approach
import java.util.*;
class GFG
{
 
  // Function to find the maximum valid
  // strings that can be formed from
  // the given frequencies
  public static int maxValidStrings(int X, int Y, int Z)
  {
 
    // Variable to store the answer
    int ans = 0;
    for (int i = 0; i < 3; i++) {
 
      // If i is greater than any of
      // the frequencies then continue
      if (i > X || i > Y || i > Z) {
        continue;
      }
 
      // Store the remaining characters left
      int xRemain = X - i;
      int yRemain = Y - i;
      int zRemain = Z - i;
 
      // Store the maximum one
      ans = Math.max(ans, i + (xRemain / 3)
                     + (yRemain / 3)
                     + (zRemain / 3));
    }
 
    // Return ans
    return ans;
  }
 
  // Driver Code
  public static void main(String[] args)
  {
    int X = 8, Y = 8, Z = 9;
 
    // Function call
    System.out.print(maxValidStrings(X, Y, Z));
  }
}
 
// This code is contributed by Taranpreet

Python3

# Python code for the above approach
 
# Function to find the maximum valid
# strings that can be formed from
# the given frequencies
def maxValidStrings( X,  Y,  Z):
 
    # Variable to store the answer
    ans = 0;
    for i in range(3):
 
        # If i is greater than any of
        # the frequencies then continue
        if (i > X or i > Y or i > Z):
            continue;
         
        # Store the remaining characters left
        xRemain = X - i;
        yRemain = Y - i;
        zRemain = Z - i;
 
        # Store the maximum one
        ans = max(ans, i + (xRemain // 3)
                           + (yRemain // 3)
                           + (zRemain // 3));
     
 
    # Return ans
    return ans;
 
# Driver Code
X = 8;
Y = 8;
Z = 9;
 
    # Function call
print(maxValidStrings(X, Y, Z));
    
# This code is contributed by Potta Lokesh

C#

// C# code to implement the approach
using System;
class GFG {
 
  // Function to find the maximum valid
  // strings that can be formed from
  // the given frequencies
  static int maxValidStrings(int X, int Y, int Z)
  {
 
    // Variable to store the answer
    int ans = 0;
    for (int i = 0; i < 3; i++) {
 
      // If i is greater than any of
      // the frequencies then continue
      if (i > X || i > Y || i > Z) {
        continue;
      }
 
      // Store the remaining characters left
      int xRemain = X - i;
      int yRemain = Y - i;
      int zRemain = Z - i;
 
      // Store the maximum one
      ans = Math.Max(ans, i + (xRemain / 3)
                     + (yRemain / 3)
                     + (zRemain / 3));
    }
 
    // Return ans
    return ans;
  }
 
  // Driver Code
  public static void Main()
  {
    int X = 8, Y = 8, Z = 9;
 
    // Function call
    Console.Write(maxValidStrings(X, Y, Z));
  }
}
 
// This code is contributed by Samim Hossain Mondal.

Javascript

<script>
    // JavaScript code to implement the approach
 
    // Function to find the maximum valid
    // strings that can be formed from
    // the given frequencies
    const maxValidStrings = (X, Y, Z) => {
     
        // Variable to store the answer
        let ans = 0;
        for (let i = 0; i < 3; i++) {
 
            // If i is greater than any of
            // the frequencies then continue
            if (i > X || i > Y || i > Z) {
                continue;
            }
 
            // Store the remaining characters left
            let xRemain = X - i;
            let yRemain = Y - i;
            let zRemain = Z - i;
 
            // Store the maximum one
            ans = Math.max(ans, i + parseInt(xRemain / 3)
                + parseInt(yRemain / 3)
                + parseInt(zRemain / 3));
        }
 
        // Return ans
        return ans;
    }
 
    // Driver Code
 
    let X = 8, Y = 8, Z = 9;
 
    // Function call
    document.write(maxValidStrings(X, Y, Z));
 
// This code is contributed by rakeshsahni
 
</script>

 
 

Output

8

 

Time Complexity: O(1)
Auxiliary Space: O(1)

 


 


Reffered: https://www.geeksforgeeks.org

Combinatorial

Related
Count of ways to choose 4 unique position elements one from each Array to make sum at most K Count of ways to choose 4 unique position elements one from each Array to make sum at most K
Count of all valid combinations of at most K numbers that sum up to N Count of all valid combinations of at most K numbers that sum up to N
Number of ways to divide a N elements equally into group of at least 2 Number of ways to divide a N elements equally into group of at least 2
Count all possible pairs in given Array with product K Count all possible pairs in given Array with product K
Maximize count of 001 and 110 that can be formed using M 0s and N 1s Maximize count of 001 and 110 that can be formed using M 0s and N 1s

Type:
 Geek
Category:
 Coding
Sub Category:
 Tutorial
Uploaded by:
 Admin
Views:
 12



 

Horje