Minimum Length of String After Deleting Similar Ends solution and explanation
9 more videos on this problem
Minimum Length of String After Deleting Similar Ends | Simple Two Pointers | Leetcode 1750codestorywithMIK · 16:09 · 10K views
Minimum Length of String after Deleting Similar Ends - Leetcode 1750 - PythonNeetCodeIO · 6:51 · 10K views
1750. Minimum Length of String After Deleting Similar Ends | 2 Pointers | Edge CasesAryan Mittal · 16:45 · 1K views
Leetcode | 1750. Minimum Length of String After Deleting Similar Ends | Medium | JavaDeveloper Docs · 8:39 · 518 views
1750. Minimum Length of String After Deleting Similar Ends (Leetcode Medium)Programming Live with Larry · 9:52 · 247 views
Leetcode 1750. Minimum Length of String After Deleting Similar EndsElite Code · 18:23 · 227 views
Minimum Length of String After Deleting Similar Ends | Daily LeetCode Solution | DSA Practice | 1750CodeMap · 18:52 · 102 views
Leetcode 1750: Minimum Length of String After Deleting Similar EndsAlgorithms Casts · 7:44 · 102 views
LeetCode 1750. [Medium] Minimum Length of String After Deleting Similar EndsFrancesco Manicardi · 4:12 · 99 views
LeetCode 1750 - Minimum Length of String After Deleting Similar Ends - PythonAlpha-Code · 7:14 · 74 views
The problem
Given a string s consisting only of characters 'a', 'b', and 'c'. You are asked to apply the following algorithm on the string any number of times:
- Pick a non-empty prefix from the string
swhere all the characters in the prefix are equal. - Pick a non-empty suffix from the string
swhere all the characters in this suffix are equal. - The prefix and the suffix should not intersect at any index.
- The characters from the prefix and suffix must be the same.
- Delete both the prefix and the suffix.
Return the minimum length of s after performing the above operation any number of times (possibly zero times).
Example 1:
Input: s = "ca" Output: 2 Explanation: You can't remove any characters, so the string stays as is.
Example 2:
Input: s = "cabaabac" Output: 0 Explanation: An optimal sequence of operations is: - Take prefix = "c" and suffix = "c" and remove them, s = "abaaba". - Take prefix = "a" and suffix = "a" and remove them, s = "baab". - Take prefix = "b" and suffix = "b" and remove them, s = "aa". - Take prefix = "a" and suffix = "a" and remove them, s = "".
Example 3:
Input: s = "aabccabba" Output: 3 Explanation: An optimal sequence of operations is: - Take prefix = "aa" and suffix = "a" and remove them, s = "bccabb". - Take prefix = "b" and suffix = "bb" and remove them, s = "cca".
Constraints:
1 <= s.length <= 105sonly consists of characters'a','b', and'c'.
Approach overview
Problem Overview: You are given a string s. If the first and last characters are the same, you can delete the entire group of identical characters from both ends. This process repeats until the characters at the ends differ or the string becomes empty. The task is to return the minimum possible length after performing these deletions.
Approach 1: Two Pointers (O(n) time, O(1) space)
This problem fits naturally with the two pointers pattern. Maintain two indices: left starting at the beginning of the string and right at the end. If s[left] and s[right] match, that character becomes the deletion target. Move left forward while characters equal this target, and move right backward while they also match it. This effectively removes the entire matching prefix and suffix group in one step.
The key insight: once the edge characters match, you must delete the entire contiguous block of that character from both sides. Partial removal is never beneficial. Each character is visited at most once by either pointer, giving linear time complexity O(n). The algorithm uses only a few integer variables, so the extra space is O(1). This is the optimal solution and the one typically expected in interviews involving string manipulation.
Approach 2: Recursive Elimination (O(n) time, O(n) recursion stack)
The same logic can be implemented recursively. If the first and last characters match, scan inward to skip all identical characters on both sides. Then recursively solve the remaining substring defined by the updated indices. Each recursive call reduces the string boundaries, mimicking the same elimination process as the iterative approach.
This approach highlights the repeated substructure of the problem: after removing symmetric groups, the remaining substring behaves exactly like the original problem. While the total number of processed characters is still linear, recursion introduces stack overhead. In the worst case, the recursion depth can reach O(n), leading to O(n) auxiliary space.
Recommended for interviews: The Two Pointers approach is the expected solution. It demonstrates strong understanding of boundary scanning and in-place reduction techniques common in two pointers problems. The recursive version is useful for reasoning about the elimination process, but interviewers typically prefer the iterative solution because it avoids recursion overhead and achieves O(1) space.
Approach 1: Two Pointers Approach
The two pointers approach uses two indices to represent the start and end of the string. The idea is to check for matching characters from both ends and shrink the string until the characters differ. Loop through the string, adjusting these pointers to remove any prefixes and suffixes with matching characters. This method is efficient as it only requires a single pass through the string.
def minimumLength(s):
left, right = 0, len(s) - 1
while left < right and s[left] == s[right]:
current_char = s[left]
while left <= right and s[left] == current_char:
left += 1
while left <= right and s[right] == current_char:
right -= 1
return right - left + 1
s = "aabccabba"
print(minimumLength(s)) # Output: 3public class Solution {
public int minimumLength(String s) {
int left = 0, right = s.length() - 1;
while (left < right && s.charAt(left) == s.charAt(right)) {
char currentChar = s.charAt(left);
while (left <= right && s.charAt(left) == currentChar) {
left++;
}
while (left <= right && s.charAt(right) == currentChar) {
right--;
}
}
return right - left + 1;
}
public static void main(String[] args) {
Solution solution = new Solution();
System.out.println(solution.minimumLength("aabccabba")); // Output: 3
}
}#include <iostream>
#include <string>
int minimumLength(std::string s) {
int n = s.size();
int left = 0, right = n - 1;
while (left < right && s[left] == s[right]) {
char currentChar = s[left];
while (left <= right && s[left] == currentChar) {
left++;
}
while (left <= right && s[right] == currentChar) {
right--;
}
}
return right - left + 1;
}
int main() {
std::string s = "aabccabba";
std::cout << minimumLength(s) << std::endl; // Output: 3
return 0;
}function minimumLength(s) {
let left = 0, right = s.length - 1;
while (left < right && s[left] === s[right]) {
const currentChar = s[left];
while (left <= right && s[left] === currentChar) {
left++;
}
while (left <= right && s[right] === currentChar) {
right--;
}
}
return right - left + 1;
}
console.log(minimumLength('aabccabba')); // Output: 3#include <stdio.h>
#include <string.h>
int minimumLength(char *s) {
int n = strlen(s);
int left = 0, right = n - 1;
while (left < right && s[left] == s[right]) {
char currentChar = s[left];
while (left <= right && s[left] == currentChar) {
left++;
}
while (left <= right && s[right] == currentChar) {
right--;
}
}
return right - left + 1;
}
int main() {
char s[] = "aabccabba";
printf("%d\n", minimumLength(s)); // Output: 3
return 0;
}using System;
public class Solution {
public int MinimumLength(string s) {
int left = 0, right = s.Length - 1;
while (left < right && s[left] == s[right]) {
char currentChar = s[left];
while (left <= right && s[left] == currentChar) {
left++;
}
while (left <= right && s[right] == currentChar) {
right--;
}
}
return right - left + 1;
}
public static void Main(string[] args) {
Solution solution = new Solution();
Console.WriteLine(solution.MinimumLength("aabccabba")); // Output: 3
}
}In this Python function, two pointers iterate from the start and end of the string. As long as the characters at the positions are equal, these characters are skipped to shrink the string effectively, resulting in the minimal remaining string's length.
Time Complexity: O(n), where n is the string size, as each position is evaluated.
Space Complexity: O(1), requiring no extra storage.
Approach 2: Recursive Elimination Approach
This recursive approach tries to minimize the string length by removing valid prefixes and suffixes. The base case is when no more valid removals are possible, and the remaining string length is minimal. Each recursive call attempts to strip away the symmetric ends and proceeds with the interior until the results match.
def recursive_length(s, left, right):
if left >= right:
return right - left + 1
if s[left] != s[right]:
return right - left + 1
current_char = s[left]
while left <= right and s[left] == current_char:
left += 1
while left <= right and s[right] == current_char:
right -= 1
return recursive_length(s, left, right)
def minimumLength(s):
return recursive_length(s, 0, len(s) - 1)
s = "aabccabba"
print(minimumLength(s)) # Output: 3public class Solution {
private int recursiveLength(String s, int left, int right) {
if (left >= right) return right - left + 1;
if (s.charAt(left) != s.charAt(right)) return right - left + 1;
char currentChar = s.charAt(left);
while (left <= right && s.charAt(left) == currentChar) {
left++;
}
while (left <= right && s.charAt(right) == currentChar) {
right--;
}
return recursiveLength(s, left, right);
}
public int minimumLength(String s) {
return recursiveLength(s, 0, s.length() - 1);
}
public static void main(String[] args) {
Solution solution = new Solution();
System.out.println(solution.minimumLength("aabccabba")); // Output: 3
}
}#include <iostream>
#include <string>
int recursiveLength(const std::string &s, int left, int right) {
if (left >= right) return right - left + 1;
if (s[left] != s[right]) return right - left + 1;
char currentChar = s[left];
while (left <= right && s[left] == currentChar) {
left++;
}
while (left <= right && s[right] == currentChar) {
right--;
}
return recursiveLength(s, left, right);
}
int minimumLength(std::string s) {
return recursiveLength(s, 0, s.size() - 1);
}
int main() {
std::string s = "aabccabba";
std::cout << minimumLength(s) << std::endl; // Output: 3
return 0;
}function recursiveLength(s, left, right) {
if (left >= right) return right - left + 1;
if (s[left] !== s[right]) return right - left + 1;
const currentChar = s[left];
while (left <= right && s[left] === currentChar) {
left++;
}
while (left <= right && s[right] === currentChar) {
right--;
}
return recursiveLength(s, left, right);
}
function minimumLength(s) {
return recursiveLength(s, 0, s.length - 1);
}
console.log(minimumLength('aabccabba')); // Output: 3#include <stdio.h>
#include <string.h>
int recursiveLength(char *s, int left, int right) {
if (left >= right) return right - left + 1;
if (s[left] != s[right]) return right - left + 1;
char currentChar = s[left];
while (left <= right && s[left] == currentChar) {
left++;
}
while (left <= right && s[right] == currentChar) {
right--;
}
return recursiveLength(s, left, right);
}
int minimumLength(char *s) {
return recursiveLength(s, 0, strlen(s) - 1);
}
int main() {
char s[] = "aabccabba";
printf("%d\n", minimumLength(s)); // Output: 3
return 0;
}using System;
public class Solution {
private int RecursiveLength(string s, int left, int right) {
if (left >= right) return right - left + 1;
if (s[left] != s[right]) return right - left + 1;
char currentChar = s[left];
while (left <= right && s[left] == currentChar) {
left++;
}
while (left <= right && s[right] == currentChar) {
right--;
}
return RecursiveLength(s, left, right);
}
public int MinimumLength(string s) {
return RecursiveLength(s, 0, s.Length - 1);
}
public static void Main(string[] args) {
Solution solution = new Solution();
Console.WriteLine(solution.MinimumLength("aabccabba")); // Output: 3
}
}This Python recursive approach continuously analyzes characters at the string's periphery, peeling symmetrical areas iteratively upon matches. The recursion simplifies the problem and calculates the minimal feasible length.
Time Complexity: O(n), similar recurrence in linear time.
Space Complexity: O(n), represented by recursion stack space demand.
Approach 3: Two pointers
We define two pointers i and j to point to the head and tail of the string s respectively, then move them to the middle until the characters pointed to by i and j are not equal, then max(0, j - i + 1) is the answer.
The time complexity is O(n) and the space complexity is O(1). Where n is the length of the string s.
function minimumLength(s: string): number {
let i = 0;
let j = s.length - 1;
while (i < j && s[i] === s[j]) {
while (i + 1 < j && s[i + 1] === s[i]) {
++i;
}
while (i < j - 1 && s[j - 1] === s[j]) {
--j;
}
++i;
--j;
}
return Math.max(0, j - i + 1);
}func minimumLength(s string) int {
i, j := 0, len(s)-1
for i < j && s[i] == s[j] {
for i+1 < j && s[i] == s[i+1] {
i++
}
for i < j-1 && s[j] == s[j-1] {
j--
}
i, j = i+1, j-1
}
return max(0, j-i+1)
}impl Solution {
pub fn minimum_length(s: String) -> i32 {
let s = s.as_bytes();
let n = s.len();
let mut start = 0;
let mut end = n - 1;
while start < end && s[start] == s[end] {
while start + 1 < end && s[start] == s[start + 1] {
start += 1;
}
while start < end - 1 && s[end] == s[end - 1] {
end -= 1;
}
start += 1;
end -= 1;
}
(0).max(end - start + 1) as i32
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Two Pointers Approach | Time Complexity: O(n), where n is the string size, as each position is evaluated. |
| Recursive Elimination Approach | Time Complexity: O(n), similar recurrence in linear time. |
| Two pointers | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Two Pointers | O(n) | O(1) | Best general solution. Efficient for large strings and typically expected in coding interviews. |
| Recursive Elimination | O(n) | O(n) | Useful for conceptual understanding of repeated boundary reduction and recursive string processing. |
Frequently asked questions
Is Minimum Length of String After Deleting Similar Ends easy or hard?
The problem is rated Medium on LeetCode with an acceptance rate around 55%. The logic becomes straightforward once you recognize the two pointers pattern and the need to remove entire matching groups from both ends.
Minimum Length of String After Deleting Similar Ends Python/Java solution
Most implementations use the same two pointer logic across languages. Maintain left and right indices, compare characters, and skip matching groups. This approach is easy to implement in Python, Java, C++, JavaScript, and C# with identical O(n) time and O(1) space complexity.
How to solve Minimum Length of String After Deleting Similar Ends in O(n)?
Use two pointers starting at the leftmost and rightmost positions. If the characters match, record that character and move both pointers inward while skipping all consecutive occurrences of it. Repeat the process until the boundary characters differ or the pointers cross. The remaining substring length is the answer.
What is the best approach for Minimum Length of String After Deleting Similar Ends?
The two pointers approach is the best solution. Use one pointer at the start and another at the end of the string. When both characters match, skip the entire contiguous block of that character from both sides. This processes each character at most once, giving O(n) time and O(1) space complexity.
Is Minimum Length of String After Deleting Similar Ends asked at Google/Amazon/Meta?
Two pointer string problems like this frequently appear in interviews at companies such as Amazon, Google, and Meta. The problem tests boundary scanning, greedy elimination, and efficient string processing. Variations also appear in coding assessments and onsite rounds.
What data structure is used in Minimum Length of String After Deleting Similar Ends?
The solution primarily uses the two pointers technique on a string. No additional data structures like stacks or hash maps are required. The algorithm works directly with indices while scanning and shrinking the string boundaries.
What is the time complexity of Minimum Length of String After Deleting Similar Ends?
The optimal algorithm runs in O(n) time where n is the length of the string. Each character is visited at most once by either the left or right pointer while skipping identical prefix and suffix groups. The space complexity of the iterative solution is O(1).