I saw this task and I was trying to solve it but I got stuck I will upload the code that I did so far. Was I close or my solution was completely wrong? And please let me know the right solution.

A string S consisting of uppercase English letters is given. In one move we can delete seven letters from S, forming the word "BALLOON" (one 'B', one 'A', two 'L's, two '0's, and one 'N'), and leave a shorter word in S. If the remaining letters in the shortened S are sufficient to allow another instance of the word "BALLOON" to be removed, next move can be done. What is the maximum number of such moves that we can apply to S?

public int solution(string S)
{
    char[] array = new char[] { 'B', 'A', 'L', 'L', 'O', 'O', 'N' };
    char[] sIntoCharacters = S.ToCharArray();
    int count = 0;
    for (int i = 0; i < sIntoCharacters.Length; i  )
    {
        for (int j = 0; j < array.Length; j  )
        {
            if (sIntoCharacters[i] == array[j])
            {
                S.Trim(new char[] { 'B', 'A', 'L', 'L', 'O', 'O', 'N' });
                count  ;
            }
        }
    }
    return count;
}

CodePudding user response：

An efficient way to do this (which is quite different from your approach) is as follows:

1. Calculate the number of occurrences of each letter in the input.
2. Calculate the number of occurrences of each letter in the target (in this case, the target is "BALLOONS").
3. For each nonzero count for a character in the target counts, calculate the input count divided by the target count.
4. Calculate the minimum value of all those divisions.

This will give you the maximum number of occurrences of the target in the input.

This has complexity O(N M) where N is the number of characters in the input and M is the number of characters in the target.

A sample implementation:

using System;
using System.Linq;

namespace Demo
{
    static class Program
    {
        public static void Main()
        {
            string input  = Randomise("BALLOONSBALLOONSBALLOONSBALLOONSABCDEFGHIJKLMNOPQRSTUVWXYS");
            string target = "BALLOONS";

            Console.WriteLine($"Input: {input}");
            Console.WriteLine($"Number of occurrences of {target} = {CountOccurrences(input, target)}");
        }

        public static string Randomise(string input)
        {
            Random rng = new Random(); // Used to randomise the input string.
            return new string(input.OrderBy(c => rng.Next()).ToArray());
        }

        public static int CountOccurrences(string input, string target)
        {
            int[] inputCounts  = CountLetters(input);
            int[] targetCounts = CountLetters(target);

            // Now for each non-zero value in targetCounts[], calculate inputCounts[x]/targetCounts[x]
            // and calculate the minimum of all those values. That will be the answer.

            int min = int.MaxValue;

            for (int i = 0; i < 26;   i)
            {
                if (targetCounts[i] != 0)
                    min = Math.Min(min, inputCounts[i]/targetCounts[i]);
            }

            // Handle the case where targetCounts[] was all zeroes, where min would still be int.MaxValue.
            return min == int.MaxValue ? 0 : min; 
        }

        public static int[] CountLetters(string text)
        {
            int[] result = new int[26]; // For 'A'..'Z' counts.

            foreach (char c in text)
            {
                int index = char.ToUpperInvariant(c) - 'A';

                if (index >= 0 && index < 26)
                      result[index];
            }

            return result;
        }
    }
}

Sample output (the "input" string will be different for each run because it is randomised, but the answer will always be 4):

Input: KNOOSSCNLLVGLLAOBNOFAWBHRSLAISSBUSLAJLBLOOXNTOBMDAOPQNOEYL
Number of occurrences of BALLOONS = 4

The Randomise() method is only there to demonstrate the solution running with a randomised input rather than something with the word "BALLOON" repeated several times. It is not actually part of the solution.