/* All the ladybugs are possible to be made happy if there is at least one empty
 * cell (underscore) and there is no color with only one ladybug. First we check
 * if there is any color with only one ladybug. If so we print "NO". Then we
 * check if there is at least one empty cell. If not, the ladybugs must already
 * be happy without moving. If there isn't any empty cell to move the ladybugs
 * around we check if all the initial positions are happy. If not we print "NO".
 * If it passes the tests we print "YES". Either the ladybugs are happy or are
 * possible to be made. In order to determine if there is any color with only
 * one ladybug we need a frequency table to hold how many times each color
 * occurs in the string. You can use an array with a size of 26 each index
 * corresponding to one letter A-Z or a hashmap to store the frequencies of each
 * color.
 */

// WITH ARRAY
class Result {
  public static String happyLadybugs(String b) {
    String happyString = "YES";
    String notHappyString = "NO";
    boolean hasUnderScore = false;
    int[] freqTable =
        new int[26]; // To store frequency of ladybugs (A-Z). A' frequency is
                     // stored at int[0] and Z's at int[25]

    // Step 1: Count frequencies of each ladybug and check for underscores
    for (char c : b.toCharArray()) {
      if (c == '_') {
        hasUnderScore = true; // Flag to track if there's at least one
                              // underscore
      } else {
        freqTable[c - 'A']++;
      }
    }

    // Step 2: Check if there's any ladybug with only 1 occurrence
    if (hasSingleOccurence(freqTable)) {
      return notHappyString;
    }

    // Step 3: If there are no underscores, check if the arrangement is already
    // happy
    if (!hasUnderScore && !isAlreadyHappy(b)) {
      return notHappyString;
    }

    // Otherwise happy
    return happyString;
  }

  // Method to check if any ladybug has only a single occurrence
  private static boolean hasSingleOccurence(int[] freq) {
    for (int i = 0; i < 26; i++) {
      if (freq[i] == 1) {
        return true;
      }
    }
    return false;
  }

  // Method to check if the string is already in a "happy" state (no
  // underscores)
  private static boolean isAlreadyHappy(String b) {
    for (int i = 0; i < b.length(); i++) {
      char current = b.charAt(i);
      if ((i > 0 && b.charAt(i - 1) == current)
          || (i < b.length() - 1 && b.charAt(i + 1) == current)) {
        continue;
      }
      return false; // found an unhappy ladybug
    }
        return true;
  }
}

    // WITH HASHMAP

    class Result {
      /*
       * Complete the 'happyLadybugs' function below.
       *
       * The function is expected to return a STRING.
       * The function accepts STRING b as parameter.
       */

      public static String happyLadybugs(String b) {
        String happyString = "YES";
        String notHappyString = "NO";
        boolean hasUnderScore = false;
        Map<Character, Integer> freqTable = new HashMap<>();

        // Step 1: Count frequencies of each ladybug and check for underscores
        for (char c : b.toCharArray()) {
          if (c == '_') {
            hasUnderScore =
                true; // Flag to track if there's at least one underscore
          } else {
            freqTable.put(c, freqTable.getOrDefault(c, 0) + 1);
          }
        }

        // Step 2: Check if there's any ladybug with only 1 occurrence
        if (hasSingleOccurence(freqTable)) {
          return notHappyString;
        }

        // Step 3: If there are no underscores, check if the arrangement is
        // already happy
        if (!hasUnderScore && !isAlreadyHappy(b)) {
          return notHappyString;
        }

        // Otherwise happy
        return happyString;
      }

      // Method to check if any ladybug has only a single occurrence
      private static boolean hasSingleOccurence(Map<Character, Integer> freq) {
        for (char key : freq.keySet()) {
          // If a character is not '_' and occurs only once, it's impossible to
          // make them happy
          if (freq.get(key) == 1) {
            return true;
          }
        }
        return false;
      }

      // Method to check if the string is already in a "happy" state (no
      // underscores)
      private static boolean isAlreadyHappy(String b) {
        for (int i = 0; i < b.length(); i++) {
          char current = b.charAt(i);
          if ((i > 0 && b.charAt(i - 1) == current)
              || (i < b.length() - 1 && b.charAt(i + 1) == current)) {
            continue;
          }
          return false; // found an unhappy ladybug
        }
        return true;
      }
    }