Alternating Characters Variant | Dataford Interview Questions

A GSK laboratory sequence-validation step receives a string containing only A and B labels. Remove the minimum number of characters so that the remaining labels alternate, meaning no two adjacent retained characters are equal. Return both the minimum deletion count and one resulting alternating string. If both possible starting patterns require the same number of deletions, return the lexicographically smaller result.

Characters may be removed but the order of all retained characters must remain unchanged.

Formal Specification

Implement minimum_deletions_to_alternate(s), where s is a non-empty string containing only A and B. Return a two-element list [deletions, result], where deletions is an integer and result is the retained alternating string.

Constraints

1 <= len(s) <= 10^5
Every character in s is either A or B
Characters can only be removed, not reordered
The output must be alternating

Function Signature

def minimum_deletions_to_alternate(s):

Your question is Alternating Characters Variant. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Problem