Scale Engineer

Minimize String Length

Easy
#2450Time: 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.
Data structures
Hash TableString

Prompt

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

  1. 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).
  2. 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.

 

Example 1:

Input: s = "aaabc"

Output: 3

Explanation:

  1. Operation 2: we choose i = 1 so c is 'a', then we remove s[2] as it is closest 'a' character to the right of s[1].
    s becomes "aabc" after this.
  2. Operation 1: we choose i = 1 so c is 'a', then we remove s[0] as it is closest 'a' character to the left of s[1].
    s becomes "abc" after this.

Example 2:

Input: s = "cbbd"

Output: 3

Explanation:

  1. Operation 1: we choose i = 2 so c is 'b', then we remove s[1] as it is closest 'b' character to the left of s[1].
    s becomes "cbd" after this.

Example 3:

Input: s = "baadccab"

Output: 4

Explanation:

  1. Operation 1: we choose i = 6 so c is 'a', then we remove s[2] as it is closest 'a' character to the left of s[6].
    s becomes "badccab" after this.
  2. Operation 2: we choose i = 0 so c is 'b', then we remove s[6] as it is closest 'b' character to the right of s[0].
    s becomes "badcca" fter this.
  3. Operation 2: we choose i = 3 so c is 'c', then we remove s[4] as it is closest 'c' character to the right of s[3].
    s becomes "badca" after this.
  4. Operation 1: we choose i = 4 so c is 'a', then we remove s[1] as it is closest 'a' character to the left of s[4].
    s becomes "bdca" after this.

 

Constraints:

  • 1 <= s.length <= 100
  • s contains 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 s into a character array chars.
  • Sort the chars array. This will group all identical characters together.
  • If the string is empty, the result is 0.
  • Initialize a counter uniqueCount to 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 one chars[i-1].
  • If they are different, it means we have encountered a new unique character, so we increment uniqueCount.
  • After the loop finishes, uniqueCount will 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.

Solutions

public class Solution { public int MinimizedStringLength ( string s ) { return new HashSet < char >( s ). Count ; } }

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.

← Previous

Previous problem

Next →

Next problem