Katkat
Back

Count Replacements Needed to Separate Equal Adjacent Characters

IBMSoftware Engineer · Online Assessment
MediumSoftware EngineerOnline AssessmentCoding & Algorithms

Last updated

This problem tests your ability to identify and process consecutive character runs in strings and apply greedy calculations to minimize replacement operations.

Problem Statement

You are given a list of strings consisting of lowercase English letters. For each string, you want to eliminate all instances of three or more consecutive identical characters (e.g., "aaa" is forbidden, but "aa" is allowed). You can replace any character in the string with a different character.

Calculate the total minimum number of replacements required across all strings in the list to ensure no character repeats three or more times consecutively. You must solve this without modifying the original strings.

Function Signature

def min_replacements_to_separate(words: List[str]) -> int:

Examples

Example 1: Input: ["aaabbb"] Output: 2 Explanation: For "aaa", you change one 'a' to get "aaba". For "bbb", you change one 'b' to get "bba". Total = 2.

Example 2: Input: ["aaaaa"] Output: 2 Explanation: Changing the 3rd 'a' gives "aabaa". Changing one more gives "aabab". Total = 2.

Constraints

  • The list contains up to 10^4 strings.
  • The total length of all strings does not exceed 10^6.
  • Characters are always lowercase English letters 'a'-'z'.

Edge Cases

  • Strings with length < 3.
  • Strings with no consecutive repeats.
  • Strings consisting entirely of the same character (e.g., "aaaaa").

Hints

Hint 1

For any run of identical characters of length L, how many replacements are needed to ensure no three are adjacent?

Hint 2

A run of length L requires floor(L / 3) replacements.

Hint 3

Iterate through each string, identify the lengths of all consecutive character runs, and sum up the required changes for each run.

Follow-up questions

  • How would the logic change if the requirement was to eliminate two or more consecutive identical characters (i.e., no two adjacent characters can be the same)?
  • What if you were allowed to delete characters instead of replacing them? How would that affect the total count?
  • Can you optimize the space complexity to O(1) beyond the input storage?