Remove Adjacent Almost-Equal Characters

Problem Description

Welcome to the world of string manipulation, where we take a perfectly good word and decide to play a game of “let’s see how many characters we can remove without causing a scene!” The problem at hand is to remove adjacent characters from a string if they are “almost equal.” Now, what does “almost equal” mean? Well, if the absolute difference between their ASCII values is 1, they are practically best friends and can be removed together.

Imagine you’re at a party, and two people are standing too close to each other, whispering sweet nothings. If their names differ by just one letter in the alphabet, you can kick them out of the party (or in this case, remove them from the string).

Solution Code


class Solution:
    def removeAlmostEqualCharacters(self, word: str) -> int:
        ans = 0
        i = 1
        while i < len(word):
            if abs(ord(word[i]) - ord(word[i - 1])) <= 1:
                ans += 1
                i += 2
            else:
                i += 1
        return ans

Approach Explanation

The code uses a simple while loop to traverse the string. It checks each pair of adjacent characters to see if they are "almost equal." If they are, it increments the count and skips the next character (because it has been removed). If not, it just moves to the next character. This continues until the end of the string is reached.

Time and Space Complexity

Complexity Type	Complexity
Time Complexity	O(n), where n is the length of the string. We traverse the string once.
Space Complexity	O(1), as we are using a constant amount of space for variables.

Real-World Example

Think of a crowded subway train where people are standing too close together. If two people are wearing similar outfits (let's say one is wearing a blue shirt and the other a navy blue shirt), they might be asked to step aside. In our string, these "similar outfits" are the characters that can be removed.

So, if you have a string like "abcde," the characters 'a' and 'b' can be removed because they are almost equal, leaving you with "cde."