Katkat
Back

Delete the Fewest Characters to Avoid Triple Repeats

DRWData Engineer · Online Assessment
EasyData EngineerOnline AssessmentCoding & Algorithms

Last updated

This problem tests string manipulation, greedy algorithm logic, and the ability to track character frequency counts to identify and prune violations of a constraint.

Problem Statement

Given a string s consisting of lowercase English letters, your goal is to remove the minimum number of characters such that the resulting string contains no sequence of three or more identical consecutive characters (e.g., "aaa" is forbidden, but "aa" is allowed).

Return the modified string after deleting the minimum number of characters required to satisfy this condition.

Function Signature

def delete_to_avoid_triples(s: str) -> str:

Constraints

  • 1 <= len(s) <= 10^5
  • s consists of lowercase English letters.

Examples

Example 1:

  • Input: s = "aaabaaa"
  • Output: "aabaa"
  • Explanation: The first "aaa" becomes "aa" (1 removal), and the last "aaa" becomes "aa" (1 removal).

Example 2:

  • Input: s = "abcde"
  • Output: "abcde"
  • Explanation: No triple repeats exist, so no deletions are needed.

Example 3:

  • Input: s = "aaaaa"
  • Output: "aa"
  • Explanation: To prevent a triple repeat, only two "a"s can remain from the initial sequence.

Edge Cases

  • Empty strings or strings with length < 3.
  • Strings consisting of only a single repeated character (e.g., "aaaa").

Hints

Hint 1

Iterate through the string while keeping track of the current consecutive character and its count.

Hint 2

Whenever the count of a repeating character reaches 3, skip adding that character to your result string.

Hint 3

Since you want to minimize deletions, you only need to remove the character when the count hits 3, rather than removing all occurrences.

Follow-up questions

  • How would you modify your solution if the requirement changed to allow no more than two identical characters *anywhere* in the string, not just consecutively?
  • What is the time and space complexity of your current solution, and can you optimize it further?
  • How would you handle this problem if you were processing a very large stream of characters where the string does not fit entirely in memory?