Is Minimum Length of String After Operations easy or hard?

The problem is rated Medium because the operations appear complex at first. Once you recognize that only character frequencies matter, the solution becomes a straightforward O(n) counting problem.

Minimum Length of String After Operations Python/Java solution

Both Python and Java implementations typically compute a frequency array of characters and derive the final length from those counts. The algorithm runs in O(n) time and requires only constant extra space for the 26 lowercase letters.

How to solve Minimum Length of String After Operations in O(n)?

Traverse the string and count the frequency of each character using an array or hash map. For each character, determine how many occurrences remain after removing valid pairs repeatedly. Summing the leftover counts across all characters gives the minimum possible length in linear time.

What is the best approach for Minimum Length of String After Operations?

The most efficient solution uses frequency counting. Count how many times each character appears and determine how many characters remain after repeatedly removing valid pairs. This approach runs in O(n) time with O(1) extra space because the alphabet size is fixed.

Is Minimum Length of String After Operations asked at Google/Amazon/Meta?

String reduction and frequency-based problems like this frequently appear in interviews at companies such as Amazon, Google, and Meta. Interviewers often use them to test string manipulation, counting techniques, and reasoning about repeated operations.

What data structure is used in Minimum Length of String After Operations?

The common data structure is a hash table or fixed-size frequency array to count characters. Some implementations also use a stack to simulate removals, but the optimized solution relies mainly on counting.

What is the time complexity of Minimum Length of String After Operations?

The optimal solution runs in O(n) time, where n is the length of the string. The algorithm scans the string once to compute character frequencies and then calculates the remaining characters in constant time per letter.

Description Hints 3 Solution Video 22:55

3223. Minimum Length of String After Operations

Medium75.0% acceptance3 companies

You are given a string s.

You can perform the following process on s any number of times:

Choose an index i in the string such that there is at least one character to the left of index i that is equal to s[i], and at least one character to the right that is also equal to s[i].
Delete the closest character to the left of index i that is equal to s[i].
Delete the closest character to the right of index i that is equal to s[i].

Return the minimum length of the final string s that you can achieve.

Example 1:

Input: s = "abaacbcbb"

Output: 5

Explanation:
We do the following operations:

Choose index 2, then remove the characters at indices 0 and 3. The resulting string is s = "bacbcbb".
Choose index 3, then remove the characters at indices 0 and 5. The resulting string is s = "acbcb".

Example 2:

Input: s = "aa"

Output: 2

Explanation:
We cannot perform any operations, so we return the length of the original string.

Constraints:

1 <= s.length <= 2 * 10⁵
s consists only of lowercase English letters.

Asked at 3 companies

IBM Amazon Bloomberg

Topics

Hints open one at a time

Hint 1

Only the frequency of each character matters in finding the final answer.

Hint 2

If a character occurs less than 3 times, we cannot perform any process with it.

Hint 3

Suppose there is a character that occurs at least 3 times in the string, we can repeatedly delete two of these characters until there are at most 2 occurrences left of it.

22:55

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
2    def minimumLength(self, s: str) -> int:
3        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2

Input

"abaacbcbb"

Input

"aa"

Your code is saved on this device.Solution