We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Remove Adjacent Almost-Equal Characters

Difficulty: Medium

Problem Description

You are given a 0-indexed string word. In one operation, you can pick any index i of word and change word[i] to any lowercase English letter. Return the minimum number of operations needed to remove all adjacent almost-equal characters from word. Two characters a and b are almost-equal if a == b or a and b are adjacent in the alphabet.

Key Insights

  • Characters can be considered almost-equal if they are the same or adjacent in the alphabet.
  • The goal is to ensure that no two adjacent characters in the final string are almost-equal.
  • The problem can be approached using a greedy strategy, where we iteratively check and modify characters as needed.
  • The changes made to the string should be minimized, leading to the final count of operations.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(1)

Solution

The approach involves iterating through the string and comparing each character with its next neighbor. If two characters are found to be almost-equal, we increment a counter and change the next character to a non-almost-equal character. The most efficient way to ensure that we are not creating new almost-equal pairs is to pick characters that are not adjacent in the alphabet.

We'll utilize a single pass through the string, keeping track of operations and modifying characters as needed. This maintains a linear time complexity.

Code Solutions

def min_operations(word: str) -> int:
    operations = 0
    n = len(word)

    for i in range(n - 1):
        if abs(ord(word[i]) - ord(word[i + 1])) <= 1:  # Check if almost-equal
            operations += 1
            # Change the next character to a non-almost-equal character
            next_char = chr((ord(word[i]) + 2) % 26 + ord('a')) if word[i] != 'z' else 'x'
            word = word[:i + 1] + next_char + word[i + 2:]

    return operations
← Back to All Questions