Construct String With Repeat Limit

class Solution {
public:
    string constructLimitedString(string str, int limit) {
        unordered_map<char, int> charCount;
        for (char c : str) {
            charCount[c]++;
        }

        priority_queue<char> characters;
        for (auto& [character, freq] : charCount) {
            characters.push(character);
        }

        string output;
        while (!characters.empty()) {
            char current = characters.top();
            characters.pop();
            int availableCount = charCount[current];

            int useCount = min(availableCount, limit);
            output.append(useCount, current);

            charCount[current] -= useCount;

            if (charCount[current] > 0 && !characters.empty()) {
                char nextCharacter = characters.top();
                characters.pop();

                output.push_back(nextCharacter);
                charCount[nextCharacter]--;

                if (charCount[nextCharacter] > 0) {
                    characters.push(nextCharacter);
                }

                characters.push(current);
            }
        }

        return output;
    }
};

This solution describes how to construct a string with a repeat limit, using C++ as the programming language. The solution accomplishes this by leveraging a priority queue to manage the characters based on their frequency in descending order, thus ensuring the highest frequency characters are processed first.

Here's a breakdown of how the solution works:

• Generate a count of each character in the input string using an unordered_map, where the key is the character and the value is its count.
• Populate a priority_queue with characters based on the character counts. This allows characters with higher frequencies to be prioritized.
• Use a loop to repeatedly pick characters from the priority_queue. On each iteration:
  1. Remove the top character, which has the highest remaining frequency.
  2. Append this character to the result string up to the given limit.
  3. Reduce the count of this used character.
  4. If there are still instances of this character left (after applying the limit):
     • Temporarily use the next highest frequency character (if available) to ensure no character is repeated more than the specified limit in succession.
     • After appending this next character, check if it still needs to be reinserted into the priority queue for future consideration along with the original character, which is reinserted as well.
• Continue the process until all characters are used or no valid characters remain to be appended while respecting the repeat limit.

The solution handles the constraints efficiently, ensuring that each character does not appear consecutively more than the allowed limit, while also managing the sequence in which characters appear in the output to maximize usage of higher frequency characters early on. This approach efficiently constructs the desired output string while adhering to the specified repeat constraints.

class Solution {

    public String constructStringWithLimits(String inputString, int maxRepeats) {
        Map<Character, Integer> charCount = new HashMap<>(); 
        for (char character : inputString.toCharArray()) {
            charCount.put(character, charCount.getOrDefault(character, 0) + 1);
        }

        PriorityQueue<Character> descendingCharQueue = new PriorityQueue<>((x, y) -> y.compareTo(x));

        for (char character : charCount.keySet()) {
            descendingCharQueue.add(character);
        }

        StringBuilder output = new StringBuilder();

        while (!descendingCharQueue.isEmpty()) {
            char currentChar = descendingCharQueue.poll();
            int currentCount = charCount.get(currentChar);

            int instancesToUse = Math.min(currentCount, maxRepeats);
            for (int i = 0; i < instancesToUse; i++) {
                output.append(currentChar);
            }

            charCount.put(currentChar, currentCount - instancesToUse);

            if (charCount.get(currentChar) > 0 && !descendingCharQueue.isEmpty()) {
                char nextChar = descendingCharQueue.poll();
                output.append(nextChar);
                charCount.put(nextChar, charCount.get(nextChar) - 1);
                if (charCount.get(nextChar) > 0) {
                    descendingCharQueue.offer(nextChar);
                }
                descendingCharQueue.offer(currentChar);
            }
        }

        return output.toString();
    }
}

The provided Java solution outlines a method to create a string from the given input string such that no character repeats consecutively more than the specified limit. Here's the summary of the approach used in the solution:

• Use a HashMap to count the frequency of each character in the input string.
• Utilize a PriorityQueue to process characters in descending order based on their natural ordering.
• Iterate over characters in priority, appending them to the result while respecting the maxRepeats limit.
• After the maximum allowed consecutive repeats of a character are appended, if the character still has remaining counts, it is temporarily skipped by introducing the next character from the queue to avoid consecutive repeats.
• Continue the process until all characters are placed in the resulting string according to the constraints.

The major steps in the algorithm are:

1. Count each character's occurrences in the input string.
2. Initialize a max-heap (priority queue) to sort characters based on their ASCII values in descending order.
3. Continue processing characters from the queue:
   • Append the current character up to the allowed limit (maxRepeats).
   • Place the next different character into the output to ensure no character is repeated consecutively beyond the allowed limit.
   • Re-insert characters back into the queue if they still have remaining counts.
4. The loop exits when no characters are left to process, returning the constructed string that meets the conditions.

class Solution:
    def constructString(self, string: str, limit: int) -> str:
        max_pq = [(-ord(char), freq) for char, freq in Counter(string).items()]
        heapify(max_pq)
        output = []

        while max_pq:
            neg_val, freq = heappop(max_pq)
            actual_char = chr(-neg_val)
            use_limit = min(freq, limit)
            output.append(actual_char * use_limit)

            if freq > use_limit and max_pq:
                next_neg_val, next_freq = heappop(max_pq)
                output.append(chr(-next_neg_val))
                if next_freq > 1:
                    heappush(max_pq, (next_neg_val, next_freq - 1))
                heappush(max_pq, (neg_val, freq - use_limit))

        return "".join(output)

The solution is designed to create a string from specified input where no characters can repeat consecutively more than a given limit. Written in Python 3, the program uses a priority queue to manage character frequencies and order of appearance, ensuring the most frequent characters are processed first within the repeat constraints.

Follow the insights below for understanding the method:

• Initialize a max priority queue that stores characters based on their ASCII negative values and their frequencies. This allows the most frequent character (highest frequency) to be accessed first.
• Convert the string input into a count of occurrences using Counter from the collections module.
• Iterate through the max priority queue:
  • Pop the character with the highest frequency.
  • Append the character to the output string restricted by the limit parameter. Use the minimum of the character's frequency or the limit.
  • If there's residual count left for that character (i.e., still more times this character needs to be appended but is constrained by limit), try to insert a different character from the priority queue to avoid consecutive repetitions.
  • Re-push the leftover frequency of characters back into the priority queue for future processing if needed.
• Continue this process until the max priority queue is emptied.
• Finally, concatenate all partial results to form the final output string.

This algorithm efficiently ensures that no single character repeats more than the limit consecutively while maintaining a greedy approach towards maximizing the use of higher frequency characters.