We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Apply Operations to Make String Empty

Number: 3308

Difficulty: Medium

Paid? No

Companies: Virtusa

Problem Description

Given a string s consisting of lowercase English letters, you repeatedly perform the following operation on s until it becomes empty: for every letter from 'a' to 'z', remove the first occurrence of that character in s (if it exists). Return the value of s immediately before you apply the last operation that makes s empty.

Key Insights

  • In each operation, at most one occurrence per letter is removed.
  • Every occurrence of a letter is removed in a sequential (round-robin) manner; that is, the k‑th occurrence of any letter is removed in the k‑th operation.
  • The total number of operations needed equals the maximum frequency (count) of any letter in s.
  • The string immediately before the final (maximum numbered) operation consists exactly of those letters whose final (maximum) occurrence is removed in the last operation.
  • By tracking the index of the k‑th occurrence for each letter, we can reconstruct the penultimate string (before final op) by selecting, for each letter that appears m times (m = max frequency), its m‑th occurrence and restoring the order of these letters as they originally appeared.

Space and Time Complexity

Time Complexity: O(n) – We traverse the string once to count frequencies and record indices, and then process a constant 26 letters. Space Complexity: O(n) – In the worst case, we might store occurrence information (or at least the index of the last occurrence) for each character.

Solution

We can solve the problem by first counting the frequency of each letter in the string. The number of operations needed to empty the string is equal to the maximum frequency among all letters. For each letter, its k‑th occurrence is removed during the k‑th operation. Thus, only those letters that appear exactly max frequency times will remain in the string immediately before the last operation, and specifically, it is their last occurrence (the max‑th occurrence) that remains. To reconstruct the penultimate state of the string, we record the index of the last occurrence (i.e. the max‑th occurrence) for every letter that occurs max times. Finally, we sort these indices in increasing order (to maintain the original order of appearance) and build the answer string.

The key data structures are: • A counter (hash table) to get letter frequencies. • An array (or dictionary) to store the last occurrence index for letters that have frequency equal to the maximum. The algorithm uses a single pass to gather frequencies and index positions, then a sort on the at most 26 elements.

Code Solutions

# Python solution with line-by-line comments
def apply_operations_to_make_string_empty(s: str) -> str:
    # Dictionary to store frequency of each character
    freq = {}
    # Dictionary to store the index of the last occurrence for each character
    last_occurrence = {}
    
    # First pass: count frequencies and record the index of each occurrence.
    for index, char in enumerate(s):
        freq[char] = freq.get(char, 0) + 1
        # Update the last occurrence index for the character
        last_occurrence[char] = index

    # Maximum frequency across all letters is the number of operations needed.
    max_ops = max(freq.values())
    
    # List to hold pairs of (index, char) for characters whose frequency equals max_ops.
    penultimate_chars = []
    
    # For each character in the frequency dictionary:
    for char, count in freq.items():
        # If the character's frequency equals the maximum number of operations,
        # its last occurrence (in the original string) is removed in the final operation.
        if count == max_ops:
            penultimate_chars.append((last_occurrence[char], char))
    
    # Sort the list by the index to maintain original order
    penultimate_chars.sort(key=lambda x: x[0])
    
    # Build the resulting string using the sorted characters.
    result = ''.join(char for idx, char in penultimate_chars)
    return result

# Example usage:
print(apply_operations_to_make_string_empty("aabcbbca"))  # Expected output: "ba"
← Back to All Questions