Problem Description

You are given a string word that is 0-indexed (meaning the first character is at index 0).

In this problem, you can perform operations on the string. In each operation, you can:

• Pick any index i in the string
• Change the character at position i to any lowercase English letter

Your goal is to find the minimum number of operations needed to ensure there are no adjacent characters in the string that are "almost-equal".

Two characters a and b are considered almost-equal if:

• They are the same character (a == b), OR
• They are adjacent letters in the alphabet (for example, 'a' and 'b' are adjacent, 'x' and 'y' are adjacent)

For example:

• 'a' and 'a' are almost-equal (same character)
• 'a' and 'b' are almost-equal (adjacent in alphabet)
• 'm' and 'n' are almost-equal (adjacent in alphabet)
• 'a' and 'c' are NOT almost-equal (not adjacent in alphabet)

The solution uses a greedy approach: it traverses the string from left to right, and whenever it finds two adjacent characters that are almost-equal, it counts one operation (to change one of them) and skips the next character to avoid unnecessary operations. This works because changing one character in a pair of almost-equal adjacent characters is sufficient to break the "almost-equal" relationship.

Intuition

When we encounter two adjacent characters that are almost-equal, we need to change one of them. The key insight is: which character should we change?

Let's think about this with an example. Suppose we have the string "aabc":

• At index 0 and 1, we have 'a' and 'a' which are almost-equal
• We could change either the first 'a' or the second 'a'

If we change the character at index 0, we only fix the relationship between indices 0 and 1. But if we change the character at index 1, we fix the relationship between indices 0 and 1, AND we also prevent any potential issues between indices 1 and 2.

This leads us to a greedy strategy: when we find two adjacent almost-equal characters at positions i-1 and i, we should change the character at position i. Why? Because:

1. Changing word[i] fixes the almost-equal relationship between word[i-1] and word[i]
2. We can choose a character for word[i] that is also different from word[i+1], potentially preventing another operation
3. After changing word[i], we can safely skip checking word[i+1] against word[i] because we've already ensured they won't be almost-equal

This is why the solution increments i by 2 (skipping the next character) after finding an almost-equal pair - we've already handled that position optimally. If no almost-equal pair is found, we simply move to the next character by incrementing i by 1.

The condition abs(ord(word[i]) - ord(word[i - 1])) < 2 checks if two characters are almost-equal by computing the absolute difference of their ASCII values. If this difference is 0 (same character) or 1 (adjacent in alphabet), the characters are almost-equal.

Learn more about Greedy and Dynamic Programming patterns.

Solution Approach

The solution implements a greedy algorithm that traverses the string from left to right, making local optimal decisions to achieve the global minimum number of operations.

Algorithm Steps:

1. Initialize variables:

   • ans = 0 to count the number of operations needed
   • i = 1 to start checking from the second character (index 1)
   • n = len(word) to store the length of the string

2. Traverse the string using a while loop while i < n:

   a. Check if characters are almost-equal:

   • Calculate abs(ord(word[i]) - ord(word[i - 1]))
   • If this value is less than 2, the characters are almost-equal
   • The ASCII difference being 0 means same character, being 1 means adjacent in alphabet

   b. If almost-equal characters are found:

   • Increment ans by 1 (we need one operation to change word[i])
   • Skip the next position by setting i += 2
   • This skip is crucial: since we're changing word[i], we can choose a character that's not almost-equal to word[i+1], so no need to check word[i+1] against the changed word[i]

   c. If characters are not almost-equal:

   • Simply move to the next position with i += 1
   • Continue checking the next pair

3. Return the result: Return ans which contains the minimum number of operations

Why this greedy approach works:

When we find an almost-equal pair at positions (i-1, i), we optimally handle it by:

• Counting one operation to change word[i]
• Skipping position i+1 because we can smartly choose the replacement character at position i to avoid conflicts with word[i+1]

This ensures we never use more operations than necessary, as we handle each conflict optimally and avoid creating new conflicts through our character choices.

Example Walkthrough

Let's walk through the algorithm with the string word = "aabc":

Initial state:

• ans = 0 (no operations yet)
• i = 1 (start checking from index 1)
• n = 4 (length of string)

Step 1: Check index 1 (comparing 'a' at index 0 with 'a' at index 1)

• Calculate: abs(ord('a') - ord('a')) = 0
• Since 0 < 2, these characters are almost-equal (same character)
• Increment ans to 1 (we need to change the 'a' at index 1)
• Skip the next position: i = i + 2 = 3

Step 2: Check index 3 (comparing 'b' at index 2 with 'c' at index 3)

• Calculate: abs(ord('c') - ord('b')) = 1
• Since 1 < 2, these characters are almost-equal (adjacent in alphabet)
• Increment ans to 2 (we need to change the 'c' at index 3)
• Skip the next position: i = i + 2 = 5

Step 3: Loop terminates

• Since i = 5 is not less than n = 4, we exit the loop
• Return ans = 2

Result: We need 2 operations to remove all almost-equal adjacent pairs.

The transformed string could be "axbd" where:

• We changed index 1 from 'a' to 'x' (fixing the 'a'-'a' pair)
• We changed index 3 from 'c' to 'd' (fixing the 'b'-'c' pair)

Note how after each change, we skip checking the next character because we can choose our replacement character wisely to avoid creating new almost-equal pairs.

Solution Implementation

Time and Space Complexity

The time complexity is O(n), where n is the length of the string word. The algorithm iterates through the string once using a while loop. In the worst case, it visits each character exactly once (when no adjacent characters are almost equal). In the best case, it might skip some characters when i += 2 is executed, but this still results in linear time complexity since each character is processed at most once.

The space complexity is O(1). The algorithm only uses a constant amount of extra space for the variables ans, i, and n, regardless of the input size. No additional data structures that scale with the input are created.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Using a For Loop Instead of While Loop

The Problem: Many developers instinctively reach for a for loop when iterating through a string:

# INCORRECT APPROACH
def removeAlmostEqualCharacters(self, word: str) -> int:
    operations_count = 0
    for i in range(1, len(word)):
        if abs(ord(word[i]) - ord(word[i - 1])) < 2:
            operations_count += 1
            # Can't skip the next iteration in a for loop!
    return operations_count

This fails because when we find almost-equal characters, we need to skip the next position (jump by 2), but a for loop will always increment by 1. This leads to overcounting operations.

Example where this fails:

• Input: "aaaa"
• Incorrect for loop result: 3 operations (counts at indices 1, 2, 3)
• Correct result: 2 operations (handles indices 1 and 3, skipping 2)

The Solution: Use a while loop with manual index control:

index = 1
while index < word_length:
    if abs(ord(word[index]) - ord(word[index - 1])) < 2:
        operations_count += 1
        index += 2  # Skip next position
    else:
        index += 1

Pitfall 2: Misunderstanding the "Almost-Equal" Definition

The Problem: Developers might incorrectly implement the almost-equal check:

# INCORRECT - only checks for same characters
if word[i] == word[i - 1]:
    operations_count += 1

# INCORRECT - wrong boundary for adjacent characters
if abs(ord(word[i]) - ord(word[i - 1])) <= 2:  # Should be < 2, not <= 2
    operations_count += 1

The second mistake would incorrectly consider 'a' and 'c' as almost-equal (difference of 2), when they should not be.

The Solution: Remember that almost-equal means:

• Difference of 0 (same character)
• Difference of 1 (adjacent in alphabet)

Therefore, use < 2 not <= 2:

if abs(ord(word[index]) - ord(word[index - 1])) < 2:

Pitfall 3: Starting from Wrong Index

The Problem: Starting iteration from index 0:

# INCORRECT
index = 0
while index < word_length:
    if abs(ord(word[index]) - ord(word[index - 1])) < 2:  # word[-1] is wrong!

This causes an index error or incorrect behavior when accessing word[index - 1] at index 0.

The Solution: Always start from index 1 since we need to compare with the previous character:

index = 1  # Start from second character
while index < word_length: