Minimum Deletions to Make Alternating String
You are given a string s consisting only of uppercase English letters. Your task is to find the minimum number of characters you need to delete from the string to make it an "alternating" string. An alternating string is defined as a string where no two adjacent characters are the same. For example, "ABABA" is an alternating string, but "AABAA" is not because of the adjacent 'AA' characters.
[ "AAAA" ]
Explanation. To make 'AAAA' alternating, we need to delete three 'A's, resulting in 'A'. Total deletions: 3.
[ "AAABBB" ]
Explanation. To make 'AAABBB' alternating, we can delete two 'A's from 'AAA' (resulting in 'A') and two 'B's from 'BBB' (resulting in 'B'). The final string would be 'AB'. Total deletions: 2 + 2 = 4.
[ "ABABAB" ]
Explanation. The string 'ABABAB' is already alternating, so no deletions are needed. Total deletions: 0.
[ "A" ]
Explanation. A single character string is always alternating. Total deletions: 0.
[ "BAABBBCCDDDAAA" ]
Explanation. Segment by segment: 'B' (0 del), 'AA' (1 del to 'A'), 'BBB' (2 del to 'B'), 'CC' (1 del to 'C'), 'DDD' (2 del to 'D'), 'AAA' (2 del to 'A'). Resulting string could be 'BABCADA'. Total deletions: 0+1+2+1+2+2 = 8.
[ "BB" ]
Explanation. To make 'BB' alternating, we delete one 'B', resulting in 'B'. Total deletions: 1.
[ "AB" ]
Explanation. The string 'AB' is already alternating. Total deletions: 0.
[ "MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM" ]
Explanation. A string of 100 identical characters ('M') requires 99 deletions to leave a single 'M'. Total deletions: 99.
Follow-up: Can you modify your function to return the resulting alternating string after performing the minimum deletions, instead of just the count of deletions?
1. The input string `s` will consist only of uppercase English letters ('A'-'Z'). 2. The length of `s` will be between 1 and 10^5, inclusive.
- Views
- 10