Minimum Length of String After Operations solution and explanation
IBM
9 more videos on this problem
Minimum Length of String After Operations | 2 Approaches |Intuition |Leetcode 3223 |codestorywithMIKcodestorywithMIK · 22:55 · 7K views
Minimum Length of String After Operations - Leetcode 3223 - PythonNeetCodeIO · 4:20 · 5K views
Minimum Length of String After Operations | Leetcode 3223Techdose · 10:00 · 4K views
3223. Minimum Length of String After Operations | Hash Map | StringsAryan Mittal · 5:51 · 3K views
3223. Minimum Length of String After Operations | leetcode daily challenge | dsa | shashcode | javaShashCode · 11:30 · 1K views
Daily Leetcode #1749: Jan 13, 2025 - 3223. Minimum Length of String After OperationsProgramming Live with Larry · 6:34 · 346 views
3223. Minimum Length of String After Operations (Leetcode Medium)Programming Live with Larry · 6:03 · 330 views
Minimum Length of String After Operations | Leetcode - 3223Algorithms Made Easy · 9:57 · 318 views
Leetcode 3223 | Minimum Length of String After Operations | Biweekly Contest 135Road To FAANG · 7:31 · 281 views
Leetcode | 3223. Minimum Length of String After Operations | Medium | JavaDeveloper Docs · 6:02 · 197 views
The problem
You are given a string s.
You can perform the following process on s any number of times:
- Choose an index
iin the string such that there is at least one character to the left of indexithat is equal tos[i], and at least one character to the right that is also equal tos[i]. - Delete the closest character to the left of index
ithat is equal tos[i]. - Delete the closest character to the right of index
ithat is equal tos[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 * 105sconsists only of lowercase English letters.
Approach overview
Problem Overview: You are given a string and allowed to perform operations that remove pairs of equal characters under specific conditions. After applying any number of valid operations, the goal is to determine the smallest possible length of the remaining string.
Approach 1: Stack-based Reduction (O(n) time, O(n) space)
This approach simulates the removal process directly. Iterate through the string and push characters onto a stack. When the current character forms a removable pattern with characters already on the stack, pop the matching elements to simulate the operation. The stack always represents the current reduced string after processing each character. Because each character is pushed and popped at most once, the total time complexity is O(n) and the auxiliary space is O(n). This method is useful when you want to model the operations exactly as described and visualize how reductions occur.
Approach 2: Two-pointer Technique with Frequency Counting (O(n) time, O(1) space)
A more optimal insight comes from observing that operations only reduce the frequency of characters in pairs. Instead of simulating every removal, count how many times each character appears using a hash table or fixed-size array for lowercase letters. For each character, repeatedly removing valid pairs leaves at most one or two occurrences depending on the count parity. Summing these remaining counts gives the final minimum length. This method scans the string once to compute frequencies and once to aggregate the result, resulting in O(n) time and O(1) extra space since the alphabet size is constant.
The key insight is that the order of operations does not affect the final count of characters that cannot be paired away. Once you know the frequency of each letter, you can determine how many characters must remain without simulating every operation. This converts what looks like a repeated string manipulation problem into a simple counting problem using a hash table or frequency array.
Recommended for interviews: Start by explaining the stack simulation because it mirrors the operation rules and shows clear reasoning about the process. Then present the optimized counting approach using counting and string analysis. Interviewers typically expect the O(n) counting solution since it avoids unnecessary simulation while still being easy to reason about.
Approach 1: Two-pointer Technique
The idea is to use two pointers, start from both ends and move towards the center to find possible deletions. By tracking pairs of identical characters, we can optimally remove pairs until no more operations are possible.
def minLength(s: str) -> int:
left, right = 0, len(s) - 1
while left < right:
if s[left] == s[right]:
l, r = left, right
while l < r and s[l] == s[r]:
l += 1
r -= 1
if l >= r:
break
left += 1
right -= 1
else:
break
return right - left + 1
s = "abaacbcbb"
print("Minimum length:", minLength(s))public class MinLength {
public static int minLength(String s) {
int left = 0, right = s.length() - 1;
while (left < right) {
if (s.charAt(left) == s.charAt(right)) {
int l = left, r = right;
while (l < r && s.charAt(l) == s.charAt(r)) {
l++;
r--;
}
if (l >= r) break;
left++;
right--;
} else {
break;
}
}
return right - left + 1;
}
public static void main(String[] args) {
String str = "abaacbcbb";
System.out.println("Minimum length: " + minLength(str));
}
}#include <iostream>
#include <string>
using namespace std;
int minLength(string s) {
int left = 0, right = s.size() - 1;
while (left < right) {
if (s[left] == s[right]) {
int l = left, r = right;
while (l < r && s[l] == s[r]) {
l++;
r--;
}
if (l >= r) break;
left++;
right--;
} else {
break;
}
}
return right - left + 1;
}
int main() {
string str = "abaacbcbb";
cout << "Minimum length: " << minLength(str) << endl;
return 0;
}function minLength(s) {
let left = 0, right = s.length - 1;
while (left < right) {
if (s[left] === s[right]) {
let l = left, r = right;
while (l < r && s[l] === s[r]) {
l++;
r--;
}
if (l >= r) break;
left++;
right--;
} else {
break;
}
}
return right - left + 1;
}
const s = "abaacbcbb";
console.log("Minimum length: " + minLength(s));#include <stdio.h>
#include <string.h>
int minLength(char* s) {
int left = 0, right = strlen(s) - 1;
while (left < right) {
if (s[left] == s[right]) {
int l = left, r = right;
while (l < r && s[l] == s[r]) {
l++;
r--;
}
if (l >= r) break;
left++;
right--;
} else {
break;
}
}
return right - left + 1;
}
int main() {
char str[] = "abaacbcbb";
printf("Minimum length: %d\n", minLength(str));
return 0;
}using System;
public class MinLength {
public static int MinLengthOf(string s) {
int left = 0, right = s.Length - 1;
while (left < right) {
if (s[left] == s[right]) {
int l = left, r = right;
while (l < r && s[l] == s[r]) {
l++;
r--;
}
if (l >= r) break;
left++;
right--;
} else {
break;
}
}
return right - left + 1;
}
public static void Main() {
string str = "abaacbcbb";
Console.WriteLine("Minimum length: " + MinLengthOf(str));
}
}Using Python, this solution again leverages the two-pointer strategy to identify and perform symmetric deletions, shrinking the string from the outer edges.
Time Complexity: O(n), Space Complexity: O(1).
Approach 2: Stack-based Reduction
Instead of using the two-pointer method, this approach uses a stack to help determine operations. As we iterate through the string, we identify characters that can be removed based on previous ones and reduce the string progressively.
def minLength(s: str) -> int:
stack = []
for char in s:
if stack and stack[-1] == char:
stack.pop()
else:
stack.append(char)
return len(stack)
s = "abaacbcbb"
print("Minimum length:", minLength(s))import java.util.Stack;
public class MinLength {
public static int minLength(String s) {
Stack<Character> stack = new Stack<>();
for (char c : s.toCharArray()) {
if (!stack.isEmpty() && stack.peek() == c) {
stack.pop();
} else {
stack.push(c);
}
}
return stack.size();
}
public static void main(String[] args) {
String str = "abaacbcbb";
System.out.println("Minimum length: " + minLength(str));
}
}#include <iostream>
#include <stack>
#include <string>
using namespace std;
int minLength(string s) {
stack<char> st;
for (char c : s) {
if (!st.empty() && st.top() == c) {
st.pop();
} else {
st.push(c);
}
}
return st.size();
}
int main() {
string str = "abaacbcbb";
cout << "Minimum length: " << minLength(str) << endl;
return 0;
}function minLength(s) {
const stack = [];
for (let char of s) {
if (stack.length > 0 && stack[stack.length - 1] === char) {
stack.pop();
} else {
stack.push(char);
}
}
return stack.length;
}
const s = "abaacbcbb";
console.log("Minimum length: " + minLength(s));#include <stdio.h>
#include <string.h>
int minLength(char* s) {
int n = strlen(s);
char stack[n];
int top = -1;
for (int i = 0; i < n; i++) {
if (top >= 0 && stack[top] == s[i]) {
top--;
} else {
stack[++top] = s[i];
}
}
return top + 1;
}
int main() {
char str[] = "abaacbcbb";
printf("Minimum length: %d\n", minLength(str));
return 0;
}using System;
using System.Collections.Generic;
public class MinLength {
public static int MinLengthOf(string s) {
Stack<char> stack = new Stack<char>();
foreach (char c in s) {
if (stack.Count > 0 && stack.Peek() == c) {
stack.Pop();
} else {
stack.Push(c);
}
}
return stack.Count;
}
public static void Main() {
string str = "abaacbcbb";
Console.WriteLine("Minimum length: " + MinLengthOf(str));
}
}The Python solution utilizes a stack to keep track of and reduce characters as we iterate. By controlling the stack, we simplify the string efficiently, removing pairs as they match.
Time Complexity: O(n), Space Complexity: O(n).
Approach 3: Counting
We can count the occurrences of each character in the string, and then iterate through the count array. If a character appears an odd number of times, then 1 of that character remains in the end; if a character appears an even number of times, then 2 of that character remain. We can sum the remaining counts of all characters to get the final length of the string.
The time complexity is O(n), where n is the length of the string s. The space complexity is O(|\Sigma|), where |\Sigma| is the size of the character set, which is 26 in this problem.
function minimumLength(s: string): number {
const cnt = new Map<string, number>();
for (const c of s) {
cnt.set(c, (cnt.get(c) || 0) + 1);
}
let ans = 0;
for (const x of cnt.values()) {
ans += x & 1 ? 1 : 2;
}
return ans;
}func minimumLength(s string) (ans int) {
cnt := [26]int{}
for _, c := range s {
cnt[c-'a']++
}
for _, x := range cnt {
if x > 0 {
if x&1 == 1 {
ans += 1
} else {
ans += 2
}
}
}
return
}Complexity comparison
| Approach | Complexity |
|---|---|
| Two-pointer Technique | Time Complexity: O(n), Space Complexity: O(1). |
| Stack-based Reduction | Time Complexity: O(n), Space Complexity: O(n). |
| Counting | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Stack-based Reduction | O(n) | O(n) | When you want to simulate the operations exactly as described and track reductions step by step |
| Two-pointer + Frequency Counting | O(n) | O(1) | Best general solution when only the final minimal length matters |
Frequently asked questions
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.