2716. Minimize String Length
Description
Given a string s
, you have two types of operation:
- Choose an index
i
in the string, and letc
be the character in positioni
. Delete the closest occurrence ofc
to the left ofi
(if exists). - Choose an index
i
in the string, and letc
be the character in positioni
. Delete the closest occurrence ofc
to 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 = 1
soc
is 'a', then we removes[2]
as it is closest 'a' character to the right ofs[1]
.
s
becomes "aabc" after this. - Operation 1: we choose
i = 1
soc
is 'a', then we removes[0]
as it is closest 'a' character to the left ofs[1]
.
s
becomes "abc" after this.
Example 2:
Input: s = "cbbd"
Output: 3
Explanation:
- Operation 1: we choose
i = 2
soc
is 'b', then we removes[1]
as it is closest 'b' character to the left ofs[1]
.
s
becomes "cbd" after this.
Example 3:
Input: s = "baadccab"
Output: 4
Explanation:
- Operation 1: we choose
i = 6
soc
is 'a', then we removes[2]
as it is closest 'a' character to the left ofs[6]
.
s
becomes "badccab" after this. - Operation 2: we choose
i = 0
soc
is 'b', then we removes[6]
as it is closest 'b' character to the right ofs[0]
.
s
becomes "badcca" fter this. - Operation 2: we choose
i = 3
soc
is 'c', then we removes[4]
as it is closest 'c' character to the right ofs[3]
.
s
becomes "badca" after this. - Operation 1: we choose
i = 4
soc
is 'a', then we removes[1]
as it is closest 'a' character to the left ofs[4]
.
s
becomes "bdca" after this.
Constraints:
1 <= s.length <= 100
s
contains only lowercase English letters
Solutions
Solution 1: Hash Table
The problem can actually be transformed into finding the number of different characters in the string. Therefore, we only need to count the number of different characters in the string.
The time complexity is $O(n)$, and the space complexity is $O(C)$. Here, $n$ is the length of the string, and $C$ is the size of the character set. In this problem, the character set is lowercase English letters, so $C=26$.
1 2 3 |
|
1 2 3 4 5 6 7 8 9 |
|
1 2 3 4 5 6 7 |
|
1 2 3 4 5 6 7 |
|
1 2 3 |
|
1 2 3 4 5 6 7 8 |
|