🔗 Menu Renewal

Given an array orders containing each customer's ordered items as strings, and an array course containing the number of menu items that make up the course dishes that "Scarpy" wants to add, complete the solution function to return, as an array of strings, the menu compositions of the new course dishes "Scarpy" will add.

• The size of the orders array is between 2 and 20, inclusive.
• Each element of the orders array is a string of length between 2 and 10, inclusive.
  • Each string consists only of uppercase alphabet letters.
  • Each string does not contain any duplicate letters.
• The size of the course array is between 1 and 10, inclusive.
  • Each element of the course array is a natural number between 2 and 10, sorted in ascending order.
  • The course array does not contain any duplicate values.
• Return the answer as an array of strings representing each course dish's composition, sorted in lexicographic ascending order.
  • The string stored in each element of the array must also be sorted in alphabetical ascending order.
  • If there are multiple menu compositions that were ordered together the most, include all of them in the array and return them.
  • The orders and course parameters are given such that the returned array's length is at least 1.

Input/Output Example #1

Same as the example in the problem.

Input/Output Example #2

AD was ordered 3 times, CD was ordered 3 times, ACD was ordered 2 times, ADE was ordered 2 times, and XYZ was ordered 2 times.

Although there is 1 customer who ordered 5 dishes, only compositions ordered by at least 2 customers become course candidates, so a course dish made up of 5 dishes is not newly added.

Input/Output Example #3

WX was ordered twice, and XY was ordered twice.

All 3 customers ordered 3 dishes each, but only compositions ordered by at least 2 customers become course candidates, so a course dish made up of 3 dishes is not newly added.

Also, since no customer ordered 4 or more dishes, a course dish made up of 4 dishes is also not newly added.

We're told to pick the most frequently ordered combination of dishes among what customers ordered, and turn it into a course dish. Let's help out.

A course dish must be made up of 2 or more individual dishes. course is assigned an array of the number of individual dishes.

If it's [ 2, 3, 4 ], we need to create course dishes made up of 2, 3, and 4 individual dishes respectively. If there are two or more dishes tied for the most ordered, make all of them into course dishes.

Based on the number of individual dishes, we can find the combinations possible from each customer's order history, then count them.

Using a HashMap object, record the order count for each course dish, and store the most frequently ordered combinations in an ArrayList to return.

Since we need to find combinations of n items from each customer's order, combinations seem appropriate.

Loop through each element of course to compute the most frequently ordered combination for each course dish size.

If an order is ABC, the course dishes made up of 2 items are AB, BC, and AC. Since AB and BA are the same combination, we need to sort each order alphabetically.

Use the Arrays.sort() method to sort each order's char[].

Then, using combinations, compute the course dish for each composition, store it in a HashMap, and separately compute the most frequently occurring count max.

Once the course dish computation is done, iterate through the HashMap's elements and store the keys with a value equal to max into an ArrayList.

Then sort the ArrayList, convert it to an array, and return it.

JAVA
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;

/**
 * Menu Renewal class
 *
 * @author RWB
 * @since 2021.12.29 Wed 11:25:03
 */
class Solution
{
	private HashMap<String, Integer> map;
	
	private int max;
	
	/**
	 * Answer return method
	 *
	 * @param orders: [String[]] Columns
	 * @param course: [int[]] Rows
	 *
	 * @return [String[]] Answer
	 */
	public String[] solution(String[] orders, int[] course)
	{
		ArrayList<String> list = new ArrayList<>();
		
		for (int item : course)
		{
			map = new HashMap<>();
			
			max = 2;
			
			for (String order : orders)
			{
				// If the ordered menu is at least the size of the course dish being added
				if (order.length() >= item)
				{
					boolean[] isVisit = new boolean[order.length()];
					
					char[] texts = order.toCharArray();
					
					Arrays.sort(texts);
					
					combination(texts, isVisit, 0, item);
				}
			}
			
			map.forEach((s, integer) ->
			{
				// If the element is the maximum value
				if (integer == max)
				{
					list.add(s);
				}
			});
		}
		
		return list.stream().sorted().toArray(String[]::new);
	}
	
	/**
	 * Combination method
	 *
	 * @param texts: [char[]] Character array
	 * @param isVisit: [boolean[]] Visited flag array
	 * @param start: [int] Starting index
	 * @param target: [int] Combination count
	 */
	private void combination(char[] texts, boolean[] isVisit, int start, int target)
	{
		// If the traversal is complete
		if (target == 0)
		{
			StringBuilder builder = new StringBuilder();
			
			for (int i = 0; i < texts.length; i++)
			{
				// If it was visited
				if (isVisit[i])
				{
					builder.append(texts[i]);
				}
			}
			
			String key = builder.toString();
			
			int value = map.getOrDefault(key, 0) + 1;
			
			map.put(key, value);
			
			max = Math.max(max, value);
		}
		
		// If not
		else
		{
			for (int i = start; i < texts.length; i++)
			{
				isVisit[i] = true;
				
				combination(texts, isVisit, i + 1, target - 1);
				
				isVisit[i] = false;
			}
		}
	}
}