Minimize String Length - Practice Coding Problems

Minimize String Length - Problem

Given a string s, you have two types of operation:

Choose an index i in the string, and let c be the character in position i. Delete the closest occurrence of c to the left of i (if exists).
Choose an index i in the string, and let c be the character in position i. Delete the closest occurrence of c to the right of i (if exists).

Your task is to minimize the length of s by performing the above operations zero or more times.

Return an integer denoting the length of the minimized string.

Input & Output

Example 1 — Basic Case

$ Input: s = "ababc"

› Output: 3

💡 Note: We can remove one 'a' and one 'b' using the operations, leaving "abc" with length 3. Since all remaining characters are unique, no further reduction is possible.

Example 2 — All Same Characters

$ Input: s = "aaa"

› Output: 1

💡 Note: We can remove the duplicates by choosing any 'a' and removing its neighbors. Eventually only one 'a' remains, giving length 1.

Example 3 — Already Unique

$ Input: s = "abc"

› Output: 3

💡 Note: All characters are already unique, so no operations are needed. The length remains 3.

Constraints

1 ≤ s.length ≤ 1000
s consists of lowercase English letters

Visualization

Tap to expand

Understanding the Visualization

Input

String with possible duplicate characters

Process

Remove duplicates using left/right deletion operations

Output

Minimum possible length (count of unique characters)

Key Takeaway

🎯 Key Insight: Only unique characters can remain after all possible deletions

Asked in

M Microsoft 15 a Amazon 12

The key insight is that no matter how we perform the deletion operations, we can only keep one instance of each unique character. The optimal approach uses a set to count unique characters in O(n) time and O(1) space for lowercase letters.

Common Approaches

Approach	Time	Space	Notes
✓ Unique Character Count	O(n)	O(k)	Count unique characters since only one of each can remain
Simulation Approach	O(n³)	O(n)	Simulate the deletion operations until no more duplicates can be removed

Unique Character Count — Algorithm Steps

Create a set to track unique characters
Iterate through string once
Add each character to set
Return size of set

Visualization

Tap to expand

Step-by-Step Walkthrough

Scan Characters

Go through each character in the string

Track Unique

Add new characters to set, ignore duplicates

Count Result

Set size equals minimum possible length

Code -

solution.c — C

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

int solution(char* s) {
    int seen[256] = {0}; // ASCII characters
    int uniqueCount = 0;
    
    for (int i = 0; s[i] != '\0'; i++) {
        if (!seen[(int)s[i]]) {
            seen[(int)s[i]] = 1;
            uniqueCount++;
        }
    }
    
    return uniqueCount;
}

int main() {
    char s[1001];
    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 through the string to count unique characters

✓ Linear Growth

Space Complexity

O(k)

Set stores at most k unique characters where k ≤ 26 for lowercase letters

✓ Linear Space

23.5K Views

Medium Frequency

~8 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

Unique Character Count — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler