How many ways can we divide a list such that each group has the same first and last members?

user_14717471 0
Viewed 259

I have an array of String called x that holds either "Boy" or "Girl". Then I want to create N groups without changing the order of x. Each group must have a minimum of 2 Strings, and the first member and the last member of the group MUST be the same String (both "Boy" or both "Girl"). Return the amount of ways to create the groups.

Example:

String[] x = {"Boy", "Boy", "Girl", "Boy", "Girl", "Girl", "Boy", "Boy"}; // Can be any length
int N = 3; // N <= x.length/2
groupCount(x, N); // Returns 2

Explanation:
The two possibilities to divide x into three groups are:

  1. ["Boy", "Boy"], ["Girl", "Boy", "Girl", "Girl"], ["Boy", "Boy"]
  2. ["Boy", "Boy", "Girl", "Boy"], ["Girl", "Girl"], ["Boy", "Boy"]

How do I implement groupCount? I've wrapped my head around it for a while. Thanks.

counter dynamic-programming function java
1 Answers

TLDR; See this implementation.

It seems to be a exercise for recursion.

Algorithm. Read the list and select the first part where the first and the ith element are the same. Remove this part from the array and decrease the number of required splits. Do it until the number is 0 or the array is empty. If the array is emtpy and the group count is 0 then it is a valid splitting. In addition, you have to select longer groups as well.

Challanges:

  • Find all valid splitting. It means your method should return with a Collection of solutions. So your input is a String[] and your return type is a String[][][] (indexes: element, group, solution). This Data Structure is hard to understand so it was wrapped in the example see ArraySlice and ArraySlices.
  • Recursion needs one more arguments which is the prefix. So you have to wrap the recursive function into you service. So the recursive implementaion cannot be called for outside of your implementaion.

Project was managed with Maven and tests were added for splitting the array. App.java can be run to demonstrate the application.

user_169757660
Related