Rack.java

import java.util.ArrayList;
import java.util.LinkedHashSet;
import java.util.LinkedHashMap;

/**
 * Represents a Rack of Scrabble tiles. This class models a rack of Scrabble tiles,
 * supporting operations to compute subsets of tiles (multisets) and their multiplicities.
*/
public class Rack {

   private String rack;
   private String rackUnique;
   private ArrayList<String> subSets;
   private int[] multiplicity;

   /**
    * Constructs a `Rack` instance from a given input string.
    * 
    * @param input the string representing the rack of tiles.
    *              It may contain duplicate characters.
   */
   public Rack(String input) {
      this.rack = input;
      this.rackUnique = getUniqueChars(input);
      this.multiplicity = getMultiplicity(input);
      this.subSets = allSubsets(this.rackUnique, this.multiplicity, 0);
   }

   /**
    * Extracts the unique characters from the input string while preserving their order.
    * 
    * @param word the input string.
    * @return a string of unique characters from the input.
   */
   public static String getUniqueChars(String word) {
      LinkedHashSet<Character> uniqueChars = new LinkedHashSet<>();
      for (int i = 0; i < word.length(); i++) {
         uniqueChars.add(word.charAt(i));
      }
      StringBuilder res = new StringBuilder();
      for (Character curChar : uniqueChars) {
         res.append(curChar);
      }
      return res.toString();
   }

   /**
    * Computes the multiplicity of each unique character in the input string.
    * 
    * @param word the input string.
    * @return an array of integers representing the count of each unique character.
   */
   public static int[] getMultiplicity(String word) {
      LinkedHashMap<Character, Integer> characterCount = new LinkedHashMap<>();
      for (int i = 0; i < word.length(); i++) {
         Character curChar = word.charAt(i);
         if (characterCount.containsKey(curChar)) {
            Integer count = characterCount.get(curChar);
            characterCount.put(curChar, count + 1);
         } else {
            characterCount.put(curChar, 1);
         }
      }
      int[] result = new int[characterCount.size()];
      int index = 0;
      for (int count : characterCount.values()) {
         result[index] = count;
         index++;
      }
      return result;
   }

   /**
    * Finds all subsets of the multiset starting at position k in unique and mult.
    * unique and mult describe a multiset such that mult[i] is the multiplicity of
    * the char
    * unique.charAt(i).
    * PRE: mult.length must be at least as big as unique.length()
    * 0 <= k <= unique.length()
    * 
    * @param unique a string of unique letters
    * @param mult   the multiplicity of each letter from unique.
    * @param k      the smallest index of unique and mult to consider.
    * @return all subsets of the indicated multiset. Unlike the multiset in the
    *         parameters,
    *         each subset is represented as a String that can have repeated
    *         characters in it.
    * @author Claire Bono
    */
   private static ArrayList<String> allSubsets(String unique, int[] mult, int k) {
      ArrayList<String> allCombos = new ArrayList<>();

      if (k == unique.length()) { // multiset is empty
         allCombos.add("");
         return allCombos;
      }

      // get all subsets of the multiset without the first unique char
      ArrayList<String> restCombos = allSubsets(unique, mult, k + 1);

      // prepend all possible numbers of the first char (i.e., the one at position k)
      // to the front of each string in restCombos. Suppose that char is 'a'...

      String firstPart = ""; // in outer loop firstPart takes on the values: "", "a", "aa", ...
      for (int n = 0; n <= mult[k]; n++) {
         for (int i = 0; i < restCombos.size(); i++) { // for each of the subsets
                                                       // we found in the recursive call
            // create and add a new string with n 'a's in front of that subset
            allCombos.add(firstPart + restCombos.get(i));
         }
         firstPart += unique.charAt(k); // append another instance of 'a' to the first part
      }

      return allCombos;
   }

   public ArrayList<String> getAllSubsets() {
      return this.subSets;
   }
}