Minimize String Length
EasyPrompt
Given a string s, you have two types of operation:
- Choose an index
iin the string, and letcbe the character in positioni. Delete the closest occurrence ofcto the left ofi(if exists). - Choose an index
iin the string, and letcbe the character in positioni. Delete the closest occurrence ofcto the right ofi(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.
Example 1:
Input: s = "aaabc"
Output: 3
Explanation:
- Operation 2: we choose
i = 1socis 'a', then we removes[2]as it is closest 'a' character to the right ofs[1].
sbecomes "aabc" after this. - Operation 1: we choose
i = 1socis 'a', then we removes[0]as it is closest 'a' character to the left ofs[1].
sbecomes "abc" after this.
Example 2:
Input: s = "cbbd"
Output: 3
Explanation:
- Operation 1: we choose
i = 2socis 'b', then we removes[1]as it is closest 'b' character to the left ofs[1].
sbecomes "cbd" after this.
Example 3:
Input: s = "baadccab"
Output: 4
Explanation:
- Operation 1: we choose
i = 6socis 'a', then we removes[2]as it is closest 'a' character to the left ofs[6].
sbecomes "badccab" after this. - Operation 2: we choose
i = 0socis 'b', then we removes[6]as it is closest 'b' character to the right ofs[0].
sbecomes "badcca" fter this. - Operation 2: we choose
i = 3socis 'c', then we removes[4]as it is closest 'c' character to the right ofs[3].
sbecomes "badca" after this. - Operation 1: we choose
i = 4socis 'a', then we removes[1]as it is closest 'a' character to the left ofs[4].
sbecomes "bdca" after this.
Constraints:
1 <= s.length <= 100scontains only lowercase English letters
Approaches
2 approaches with complexity analysis and trade-offs.
This approach is based on the realization that the operations allow us to remove any duplicate characters, ultimately leaving only one of each unique character. The problem thus simplifies to counting the number of unique characters in the string. A straightforward way to count unique elements is to sort the collection first, which groups identical elements together, making them easy to count.
Algorithm
- Convert the input string
sinto a character arraychars. - Sort the
charsarray. This will group all identical characters together. - If the string is empty, the result is 0.
- Initialize a counter
uniqueCountto 1, accounting for the first character in the sorted array. - Iterate through the sorted array from the second element (
i = 1). - In each iteration, compare the current character
chars[i]with the previous onechars[i-1]. - If they are different, it means we have encountered a new unique character, so we increment
uniqueCount. - After the loop finishes,
uniqueCountwill hold the total number of distinct characters.
Walkthrough
The core idea is that the complex deletion operations described in the problem statement effectively allow for the removal of any duplicate character. If a character appears more than once, we can always find two occurrences and eliminate one. This can be repeated until only one instance of that character remains. This logic applies to all characters in the string. Therefore, the minimum possible length of the string is simply the number of unique characters present in the original string.
To implement this, we first convert the string to a character array. Then, we sort this array using a standard sorting algorithm. After sorting, all occurrences of the same character will be adjacent to each other. We can then iterate through the sorted array once to count the unique characters. We start a counter at 1 (assuming the string is not empty) and increment it every time we find a character that is different from the one immediately preceding it.
For example, if s = "baadccab", the sorted character array would be ['a', 'a', 'a', 'b', 'b', 'c', 'c', 'd']. By scanning this array, we can count the unique characters: 'a', 'b', 'c', and 'd', for a total of 4.
import java.util.Arrays; class Solution { public int minimizedStringLength(String s) { if (s == null || s.length() == 0) { return 0; } char[] chars = s.toCharArray(); Arrays.sort(chars); int uniqueCount = 1; for (int i = 1; i < chars.length; i++) { if (chars[i] != chars[i - 1]) { uniqueCount++; } } return uniqueCount; }}Complexity
Time
O(N log N), where N is the length of the string. The dominant part of this algorithm is the sorting step, which typically has a time complexity of O(N log N).
Space
O(N), where N is the length of the string. This is because in Java, strings are immutable, so we need to create a new character array of size N to perform the sort.
Trade-offs
Pros
The logic is relatively simple and easy to follow.
It correctly determines the number of unique characters, which is the solution to the problem.
Cons
This approach is less efficient than linear time solutions due to the sorting step.
It requires extra space to hold the character array, as strings are immutable in Java.
The most efficient approach recognizes that the problem simplifies to counting unique characters. Instead of sorting, we can use a data structure that provides constant-time average insertion and lookup to keep track of the characters we have already seen. A HashSet is ideal for this purpose. Given the constraint that characters are only lowercase English letters, a simple boolean array can also serve as a highly efficient frequency map.
Algorithm
-
Using a HashSet:
- Initialize an empty
HashSet<Character>nameduniqueChars. - Iterate through each character
cof the input strings. - For each character, add it to the
uniqueCharsset. The set will automatically handle duplicates; adding an existing element has no effect. - After the loop, the size of the
uniqueCharsset is the number of distinct characters. Return this size.
- Initialize an empty
-
Using a Frequency Array:
- Since the input consists of only lowercase English letters, we can use a boolean array
seenof size 26. - Initialize the
seenarray with allfalsevalues. - Initialize a counter
uniqueCountto 0. - Iterate through each character
cof the input strings. - For each character, calculate its corresponding index in the array (
index = c - 'a'). - If
seen[index]isfalse, it means this is the first time we've encountered this character. Setseen[index]totrueand incrementuniqueCount. - After the loop, return
uniqueCount.
- Since the input consists of only lowercase English letters, we can use a boolean array
Walkthrough
This optimal approach is also based on the insight that the operations allow for the removal of all duplicate characters, reducing the problem to counting the distinct characters in the string. We can achieve this in linear time.
Method 1: Using a HashSet
A HashSet stores only unique elements. We can iterate through the input string and add each character to a HashSet. The set's internal logic ensures that duplicates are not stored. After iterating through the entire string, the size of the HashSet will give us the count of unique characters.
import java.util.HashSet;import java.util.Set; class Solution { public int minimizedStringLength(String s) { Set<Character> uniqueChars = new HashSet<>(); for (char c : s.toCharArray()) { uniqueChars.add(c); } return uniqueChars.size(); }}Method 2: Using a Frequency Array
Since the problem specifies that the string contains only lowercase English letters (a-z), we can use a simple boolean array of size 26 as a direct address table or frequency map. Each index in the array corresponds to a letter of the alphabet. We iterate through the string, and for each character, we mark its corresponding index in the array as true. We can also maintain a counter that increments only when we see a character for the first time. This avoids a second pass over the frequency array.
class Solution { public int minimizedStringLength(String s) { boolean[] seen = new boolean[26]; int uniqueCount = 0; for (char c : s.toCharArray()) { if (!seen[c - 'a']) { seen[c - 'a'] = true; uniqueCount++; } } return uniqueCount; }}Both methods are highly efficient and perfectly suited for this problem.
Complexity
Time
O(N), where N is the length of the string. We perform a single pass through the string. Operations like adding to a `HashSet` or accessing an array index take constant time on average.
Space
O(1). The `HashSet` will store at most 26 characters, and the boolean array has a fixed size of 26. In both cases, the space used is constant and does not depend on the length of the input string.
Trade-offs
Pros
Optimal time complexity of O(N).
Optimal space complexity of O(1) because the alphabet size is constant.
Very simple and concise to implement.
Cons
There are no significant cons for this approach as it is optimal for the given constraints.
Solutions
Solution
public class Solution { public int MinimizedStringLength ( string s ) { return new HashSet < char >( s ). Count ; } }class Solution {public int minimizedStringLength(String s) { Set<Character> ss = new HashSet<>(); for (int i = 0; i < s.length(); ++i) { ss.add(s.charAt(i)); } return ss.size(); }}class Solution {public: int minimizedStringLength(string s) { unordered_set<char> ss(s.begin(), s.end()); return ss.size(); }};class Solution: def minimizedStringLength(self, s: str) -> int: return len(set(s))Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.