3039. Apply Operations to Make String Empty

MediumArrayHash TableCountingSorting
Leetcode Link

Problem Description

The task is to repeatedly delete the first occurrence of each alphabet character in a string s from 'a' to 'z', until the string becomes empty. At each stage, only one occurrence of each letter is removed, if that letter is present in the string. This operation is carried out repeatedly. The goal is to find the string s right before the last round of the operation is applied. In simpler terms, we want to know what s looks like when it contains just enough characters for one last complete pass (removing 'a' to 'z' sequence). For example, if we begin with s = "aabcbbca", after performing these operations consecutively, prior to the final operation that empties it, the string is reduced to "ba".

Intuition

To compute the string right before the last operation, the core idea relies on the observation that only the characters that have the highest frequency will be potentially left before the final removal (because all others will get eliminated in earlier rounds). So our approach involves two main steps:

  1. Count the frequency of each character in the string. The character(s) with the maximum frequency will determine the number of operations needed before the string becomes empty, as they define the 'pace' at which the string is reduced through each operation set.

  2. For each character that has the maximum frequency, we need to check if its current position in the string corresponds to the last occurrence of that character. If both conditions hold true for a character (maximum frequency and the position is the last occurrence), it will survive until right before the final operation.

To implement this idea:

  • Use a data structure like a hash table or Counter (in Python) to record the number of occurrences of each character in the string. Determine the maximum occurrence count mx.

  • Create another hash table to record the last occurrence index of each character in the string.

  • Iterate through the string and for each character, check if the number of occurrences is equal to mx and its index is the last occurrence. If so, this character is part of the string right before the last deletion operation.

  • Combine all such characters that meet the criteria to form the desired result.

By following this solution approach, we can ensure that only the characters that could possibly remain till the penultimate operation are included in the final string.

Learn more about Sorting patterns.

Solution Approach

The provided solution uses the Counter class from the Python collections module to efficiently count the occurrences of each character in the string. An additional dictionary, last, is created to store the index of the last occurrence of each character in the string. This approach leverages hash tables (dictionaries in Python), which offer efficient O(1) average time complexity for lookup, insert, and update operations. This is vital for keeping the overall solution efficient.

The implementation steps are as follows:

  1. Count Occurrences: A Counter object, cnt, captures the frequency of each character by iterating over the string once (O(n) time complexity, where n is the length of s).

  2. Find Maximum Frequency: The most_common method of the Counter object is then used to find character frequency, mx, that occurs most often (O(k) time complexity, where k is the number of distinct characters in the string; typically k <= 26).

  3. Record Last Index: A dictionary, last, maps each character to the last index at which it appears in the string. This also involves iterating over the string once.

  4. Construct Result String: Finally, the program iterates through s again and includes a character c in the result only if c meets both of the following conditions:

  • cnt[c] == mx: The occurrence count of c matches the maximum frequency. This ensures we only consider characters that can last until just before the final operation.
  • last[c] == i: The current index i is the last occurrence index of c. This condition ensures that for a character to be included in the final string, it must be the last one of its kind within s.

These combined conditions ensure we only append to the resulting string those characters that will be removed in the last operation. This guarantees the string constructed will be the exact string available right before the last operation is performed.

By iterating through the characters and checking these conditions, the solution constructs the answer in a single pass, i.e., in O(n) time complexity, which makes the overall algorithm run in linear time with respect to the length of the input string.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which of these pictures shows the visit order of a depth-first search?

Example Walkthrough

Let's illustrate the solution approach using the example string s = "aabcddcbba".

  1. Count Occurrences: We first count the occurrences of each character using a Counter object.

    • {'a': 3, 'b': 3, 'c': 2, 'd': 2}
  2. Find Maximum Frequency: Using the most_common method of the Counter object, we find the maximum occurrence frequency, mx.

    • mx = 3 (both 'a' and 'b' occur 3 times)
  3. Record Last Index: We record the last index where each character appears in the string.

    • {'a': 8, 'b': 9, 'c': 7, 'd': 4}
  4. Construct Result String: We iterate through s from left to right, checking if each character meets the conditions to be appended to the result.

    • First 'a' at index 0: cnt['a'] == mx is True, but last['a'] == 0 is False. We do not include this 'a'.
    • Second 'a' at index 1: cnt['a'] == mx is True, but last['a'] == 1 is False. We do not include this 'a'.
    • Third 'a' at index 8: cnt['a'] == mx is True and last['a'] == 8 is also True. We include this 'a'.
    • Apply similar logic to other characters.

Result would include the third 'a' and the second 'b' because those are the last occurrences and they also have the maximum frequency (mx). No other character satisfies both conditions, so they will all have been removed before the penultimate operation.

Hence, right before the last round that removes 'a' to 'z', string s looks like "ab".

Solution Implementation

1from collections import Counter
2
3class Solution:
4    def lastNonEmptyString(self, s: str) -> str:
5        # Create a counter object to count occurrences of each character in the string.
6        char_count = Counter(s)
7      
8        # Find the maximum count of any character in the string.
9        max_count = char_count.most_common(1)[0][1]
10      
11        # Create a dictionary to record the last known index of each character.
12        last_index = {char: idx for idx, char in enumerate(s)}
13      
14        # Build the result string comprising characters with the maximum count and
15        # only include the character if it's the last occurrence in the string.
16        result = "".join(char for idx, char in enumerate(s) if char_count[char] == max_count and last_index[char] == idx)
17      
18        return result
19
1class Solution {
2    public String lastNonEmptyString(String s) {
3        // Create an array to count occurrences of each letter
4        int[] count = new int[26];
5        // Create an array to keep track of the last occurrence index of each letter
6        int[] lastIndex = new int[26];
7        int length = s.length();
8        // mx represents the maximum occurrences of any character
9        int maxOccurrences = 0;
10      
11        // Loop through the string to fill count and lastIndex arrays
12        for (int i = 0; i < length; ++i) {
13            int charIndex = s.charAt(i) - 'a';
14            count[charIndex]++;
15            // Update maximum occurrences found so far
16            maxOccurrences = Math.max(maxOccurrences, count[charIndex]);
17            // Update the last occurrence index of the current character
18            lastIndex[charIndex] = i;
19        }
20      
21        // StringBuilder to construct the final answer
22        StringBuilder answer = new StringBuilder();
23      
24        // Loop through the string to find out the characters to append to the answer
25        for (int i = 0; i < length; ++i) {
26            int charIndex = s.charAt(i) - 'a';
27            // Include the character if it occurs the maximum number of times
28            // and the current index is the last occurrence of that character
29            if (count[charIndex] == maxOccurrences && lastIndex[charIndex] == i) {
30                answer.append(s.charAt(i));
31            }
32        }
33      
34        // Return the final string
35        return answer.toString();
36    }
37}
38
1class Solution {
2public:
3    // Function to find the last sequence of max repeated characters
4    string lastNonEmptyString(string str) {
5        // Array to store the count of each alphabet
6        int count[26] = {0};
7        // Array to store the index of last occurrence of each alphabet
8        int lastOccurrence[26] = {0};
9        int stringLength = str.size();
10        int maxCount = 0; // Variable to store the maximum count found so far
11
12        // Loop to count occurrences and to find the last position of each character
13        for (int i = 0; i < stringLength; ++i) {
14            int charIndex = str[i] - 'a'; // Convert character to index (0-25)
15            // Update the occurrence count for this character
16            maxCount = max(maxCount, ++count[charIndex]);
17            // Update the last position of occurrence for this character
18            lastOccurrence[charIndex] = i;
19        }
20
21        // String to store the answer
22        string result;
23        // Loop to build the answer string with characters of max count and are at their last occurrence
24        for (int i = 0; i < stringLength; ++i) {
25            int charIndex = str[i] - 'a';
26            // Check if the current character has the max count and it is the last occurrence
27            if (count[charIndex] == maxCount && lastOccurrence[charIndex] == i) {
28                result.push_back(str[i]);
29            }
30        }
31
32        // Return the resulting string
33        return result;
34    }
35};
36
1// Returns the last string comprised of the most frequently occurred character in the input string `s`,
2// considering only its last occurrence when multiple characters occur with the same maximum frequency.
3function lastNonEmptyString(s: string): string {
4    // Initialize an array `count` with 26 zeroes to store the frequency of each lowercase alphabet letter.
5    const count: number[] = Array(26).fill(0);
6
7    // Initialize an array `lastIndex` with 26 zeroes to remember the last occurrence index of each letter.
8    const lastIndex: number[] = Array(26).fill(0);
9
10    // Get the length of the input string.
11    const lengthOfString = s.length;
12
13    // Initialize `maxFrequency` to keep track of the highest frequency of any character in `s`.
14    let maxFrequency = 0;
15
16    // Iterate through the input string to populate `count` and `lastIndex` arrays.
17    for (let i = 0; i < lengthOfString; ++i) {
18        // Calculate the index corresponding to the current character (assuming 'a' to 'z' characters).
19        const charIndex = s.charCodeAt(i) - 97;
20      
21        // Increment the count for this character and update `maxFrequency` if necessary.
22        maxFrequency = Math.max(maxFrequency, ++count[charIndex]);
23
24        // Update the last occurrence index for this character.
25        lastIndex[charIndex] = i;
26    }
27
28    // Initialize an array `resultStrings` to hold characters that meet the criteria for output.
29    const resultStrings: string[] = [];
30
31    // Iterate over the input string to determine the result characters.
32    for (let i = 0; i < lengthOfString; ++i) {
33        // Calculate the index as before to access the count and last occurrence index.
34        const charIndex = s.charCodeAt(i) - 97;
35
36        // Check if the current character's count matches `maxFrequency` and the character is the last occurrence.
37        if (count[charIndex] === maxFrequency && lastIndex[charIndex] === i) {
38            // If the character meets the criteria, add the character to the result array.
39            resultStrings.push(String.fromCharCode(charIndex + 97));
40        }
41    }
42
43    // Join the array of result characters into a string and return the result.
44    return resultStrings.join('');
45}
46

Time and Space Complexity

The time complexity of the provided code is O(n) where n is the length of the input string s. This is because the code iterates over the string multiple times independently: first, to count the occurrences of each character using Counter, and then to create a dictionary with the index of the last occurrence of each character. Finally, it iterates over the string again to build the result string.

The space complexity is O(|Σ|) where |Σ| is the size of the character set which, in the case of lowercase English letters, is 26. The space used by the Counter object and the last occurrence dictionary both depend on the number of different characters in the string, not the size of s itself.

Learn more about how to find time and space complexity quickly using problem constraints.


Fast Track Your Learning with Our Quick Skills Quiz:

How does quick sort divide the problem into subproblems?


Recommended Readings


Got a question? Ask the Monster Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

Tired of the LeetCode Grind?

Our structured approach teaches you the patterns behind problems, so you can confidently solve any challenge. Get started now to land your dream tech job.

Get Started

🪄