Skip to content
Onsite
15 / 19

Minimum Deletions to Make a Good String

MediumP3Coding

Call a string good if its length is even and, for each pair of positions (1, 2), (3, 4), ..., the two characters are different. The empty string is good. For example "good", "string" and "xyyx" are good, while "bad", "aa" and "aabc" are not.

Given a string s, return the minimum number of characters to delete from it (keeping the remaining characters in their original order) so that it becomes good.

Example 1

Input
s = "good"
Output
0

Example 2

Input
s = "aabc"
Output
2
Why
Delete one a and the c to get "ab".

Example 3

Input
s = "aa"
Output
2

Constraints

  • 1 <= s.length <= 2 * 10^5
  • s consists of lower-case English letters

Hints

Run checks the 3 visible tests, Submit all 12.