Minimum Length of String After Deleting Similar Ends

Minimum Length of String After Deleting Similar Ends - 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 s where all the characters in the prefix are equal.
Pick a non-empty suffix from the string s where 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 suffix.

Return the minimum length of s after performing the above operation any number of times (possibly zero times).

Input & Output

Example 1 — Basic Removal

$ Input: s = "caabbc"

› Output: 0

💡 Note: Remove prefix "c" and suffix "c" → "aabb". Then remove prefix "aa" and suffix "bb" → "". Final length is 0.

Example 2 — Partial Removal

$ Input: s = "aabccabba"

› Output: 3

💡 Note: Remove prefix "aa" and suffix "a" → "bccabb". Remove prefix "b" and suffix "bb" → "cca". No more removals possible. Final length is 3.

Example 3 — No Removal

$ Input: s = "abc"

› Output: 3

💡 Note: No matching prefix-suffix pairs exist (a ≠ c, b can't form both prefix and suffix without overlap). Final length is 3.

Constraints

1 ≤ s.length ≤ 10⁵
s consists only of characters 'a', 'b', and 'c'

Visualization

Tap to expand

Understanding the Visualization

Input

String with characters a, b, c

Process

Remove matching prefix-suffix pairs layer by layer

Output

Minimum remaining length after all possible removals

Key Takeaway

🎯 Key Insight: Use two pointers to greedily remove the longest matching character layers from both ends

Asked in

f Facebook 25 a Amazon 20 G Google 18

The key insight is to greedily remove the longest possible matching prefix-suffix pairs using two pointers. Best approach uses two pointers moving inward to efficiently identify and remove character layers. Time: O(n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Two Pointers - Greedy Approach	O(n)	O(1)	Use two pointers to greedily remove matching character layers from both ends
Brute Force - Try All Combinations	O(3ⁿ)	O(n)	Try every possible prefix-suffix combination recursively

Two Pointers - Greedy Approach — Algorithm Steps

Initialize left and right pointers at string ends
Find longest matching prefix-suffix pair of same character
Remove the matching parts and update pointers
Repeat until no more matching pairs can be found

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize Pointers

Left at start, right at end

Find Matching Layer

Extend matching prefix and suffix

Remove and Continue

Update pointers and repeat

Code -

solution.c — C

#include <stdio.h>
#include <string.h>

int solution(char* s) {
    int n = strlen(s);
    int left = 0, right = n - 1;
    
    while (left < right) {
        if (s[left] != s[right]) {
            break;
        }
        
        // Find the longest prefix of same character
        char ch = s[left];
        int leftEnd = left;
        while (leftEnd <= right && s[leftEnd] == ch) {
            leftEnd++;
        }
        
        // Find the longest suffix of same character
        int rightStart = right;
        while (rightStart >= left && s[rightStart] == ch) {
            rightStart--;
        }
        
        // Update pointers to remove the matching prefix and suffix
        left = leftEnd;
        right = rightStart;
    }
    
    int result = right - left + 1;
    return result < 0 ? 0 : result;
}

int main() {
    char s[1001];
    fgets(s, sizeof(s), stdin);
    s[strcspn(s, "\n")] = 0;
    printf("%d\n", solution(s));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass through string with two pointers, each character visited at most once

✓ Linear Growth

Space Complexity

O(1)

Only using two pointer variables and character counters

✓ Linear Space

28.0K Views

Medium Frequency

~15 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Two Pointers - Greedy Approach — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler