Minimum Length of String After Operations

Minimum Length of String After Operations - Problem

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 occurrence of s[i] located to the left of i.

Delete the closest occurrence of s[i] located to the right of i.

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

Input & Output

Example 1 — Basic Case

$ Input: s = "aabcca"

› Output: 5

💡 Note: Character frequencies: a=3, b=1, c=2. Each contributes min(freq, 2): a contributes 2, b contributes 1, c contributes 2. Total: 2+1+2=5

Example 2 — All Different

$ Input: s = "abc"

› Output: 3

💡 Note: All characters appear only once, so no operations possible. Final length equals original length: 3

Example 3 — High Frequency

$ Input: s = "aaaa"

› Output: 2

💡 Note: Character 'a' appears 4 times, but can only contribute 2 to final result. Operations can reduce 4 a's to 2 a's

Constraints

1 ≤ s.length ≤ 2 × 10⁵
s consists of lowercase English letters only

Visualization

Tap to expand

Understanding the Visualization

Input

String with character frequencies

Process

Remove triplet patterns optimally

Output

Minimum achievable length

Key Takeaway

🎯 Key Insight: Characters appearing 3+ times can be reduced to at most 2 through optimal removal operations

Asked in

G Google 25 f Meta 20 a Amazon 18

The key insight is that each character can appear at most 2 times in the final string. Characters with frequency ≥ 3 can be reduced through removal operations. The frequency counting approach directly calculates the answer by taking min(frequency, 2) for each character. Time: O(n), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Frequency Count Optimization	O(n)	O(1)	Count character frequencies and determine optimal final arrangement mathematically
Simulation Approach	O(n³)	O(n)	Repeatedly find valid operations and perform deletions until no more operations possible

Frequency Count Optimization — Algorithm Steps

Count frequency of each character
For each char with freq ≥ 3, reduce to at most 2
Sum remaining characters

Visualization

Tap to expand

Step-by-Step Walkthrough

Count

Count frequency of each character

Analyze

Each character contributes min(frequency, 2)

Sum

Add up contributions for final answer

Code -

solution.c — C

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

int solution(char* s) {
    int freq[256] = {0};
    int len = strlen(s);
    
    // Count frequency of each character
    for (int i = 0; i < len; i++) {
        freq[(unsigned char)s[i]]++;
    }
    
    // Calculate minimum possible length
    int result = 0;
    for (int i = 0; i < 256; i++) {
        if (freq[i] > 0) {
            // Each character can contribute at most 2 to final result
            // If count >= 3, we can reduce it by removing triplets
            result += (freq[i] > 2) ? 2 : freq[i];
        }
    }
    
    return result;
}

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

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass to count frequencies plus O(26) to process character counts

✓ Linear Growth

Space Complexity

O(1)

Hash map stores at most 26 characters for lowercase English letters

✓ Linear Space

23.4K 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

Frequency Count Optimization — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler