LeetCode Problem 2957

Difficulty: 🟡 Medium
Topics: String, Dynamic Programming, Greedy

Solution

LeetCode 2957 - Remove Adjacent Almost-Equal Characters

Problem Understanding

We are given a string word consisting of lowercase English letters.

Two adjacent characters are considered almost-equal if either:

• They are exactly the same, such as 'a' and 'a'
• Their positions in the alphabet differ by exactly one, such as 'a' and 'b', 'c' and 'b', 'x' and 'y'

The goal is to perform the minimum number of operations so that no adjacent pair in the final string is almost-equal.

In a single operation, we may choose any index and replace that character with any lowercase English letter. Since we can change a character to any letter we want, each modification is very powerful.

The input is a single string word, and the output is the minimum number of character replacements required to eliminate all adjacent almost-equal pairs.

The constraints are very small:

• 1 <= word.length <= 100
• Only lowercase English letters appear

Because the string length is at most 100, many approaches would be fast enough. However, the challenge is finding the minimum number of modifications and understanding the structure of the problem.

Some important edge cases include:

• A string of length 1, which already satisfies the condition.
• Long runs of identical characters such as "aaaaaa".
• Chains of consecutive letters such as "abcdef", where every adjacent pair is almost-equal.
• Overlapping violations, where fixing one pair may also affect neighboring pairs.

The key observation is that one modification can eliminate violations involving adjacent positions, so we must avoid counting violations independently.

Approaches

Brute Force

A brute-force solution would try all possible character replacements and search for the minimum number of changes required.

For each position, we could either keep the original character or replace it with one of 25 other letters. We would then check whether the resulting string contains any adjacent almost-equal characters.

This guarantees correctness because every possible modified string is examined. However, the number of possibilities grows exponentially. Even for a length-100 string, exploring all combinations is completely infeasible.

Therefore, although brute force finds the optimal answer, it is far too slow.

Key Insight

Consider scanning the string from left to right.

Whenever positions i and i+1 form an almost-equal pair, at least one of those two characters must eventually be changed.

Since a replacement can be chosen arbitrarily, we can always modify the second character in the pair so that it is not almost-equal to either neighbor.

Suppose we encounter a bad pair (i, i+1).

Instead of trying many possibilities, we can greedily decide to "fix" this pair with one operation and then skip both positions.

Why is this valid?

If (i, i+1) is almost-equal, any valid final solution must modify at least one character from this pair. Performing one operation immediately is unavoidable. Furthermore, changing one character can eliminate all violations involving that pair, so the optimal strategy is simply to count disjoint bad pairs.

This becomes identical to finding the minimum number of changes needed when scanning adjacent pairs greedily:

• If (i, i+1) is bad, count one operation and skip both positions.
• Otherwise move one position forward.

This greedy strategy is optimal because every detected bad pair requires at least one modification, and one modification is always sufficient.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	Exponential	Exponential	Tries all possible character replacements
Optimal Greedy	O(n)	O(1)	Counts disjoint almost-equal adjacent pairs

Algorithm Walkthrough

1. Initialize operations = 0.
2. Start scanning the string from left to right using index i = 0.
3. For each adjacent pair (word[i], word[i+1]), determine whether they are almost-equal.
4. Two characters are almost-equal if:

• They are identical, or
• Their ASCII codes differ by exactly 1

5. If the pair is almost-equal:

• Increment operations by 1.
• Skip both positions by setting i += 2.
• This represents using one modification to fix the pair.

6. Otherwise:

• Move to the next position with i += 1.

7. Continue until i reaches the second-to-last character.
8. Return operations.

Why it works

Whenever an almost-equal pair is encountered, at least one character from that pair must be modified in any valid solution. Therefore, every such pair contributes at least one required operation.

By greedily fixing the pair and skipping both characters, we effectively choose a modification that removes the violation. Since a replacement character can be selected freely, one modification is always sufficient. The greedy scan ensures that overlapping violations are handled optimally, and no unnecessary operations are counted.

Python Solution

class Solution:
    def removeAlmostEqualCharacters(self, word: str) -> int:
        operations = 0
        i = 0
        n = len(word)

        while i < n - 1:
            if abs(ord(word[i]) - ord(word[i + 1])) <= 1:
                operations += 1
                i += 2
            else:
                i += 1

        return operations

The implementation follows the greedy algorithm directly.

The variable operations stores the number of modifications required. The pointer i scans the string from left to right.

For each adjacent pair, we compute:

abs(ord(word[i]) - ord(word[i + 1]))

If the difference is 0 or 1, the pair is almost-equal. In that situation, one modification is necessary, so we increment the answer and skip both positions.

If the pair is already valid, we simply advance to the next index.

After the scan completes, operations contains the minimum number of required changes.

Go Solution

func removeAlmostEqualCharacters(word string) int {
    operations := 0
    n := len(word)

    for i := 0; i < n-1; {
        diff := int(word[i]) - int(word[i+1])
        if diff < 0 {
            diff = -diff
        }

        if diff <= 1 {
            operations++
            i += 2
        } else {
            i++
        }
    }

    return operations
}

The Go implementation mirrors the Python solution.

Since Go does not provide a built-in absolute value function for integers in the standard language syntax, we manually compute the absolute difference between the two byte values.

The string contains only lowercase English letters, so indexing directly into the string is safe because every character occupies exactly one byte.

Worked Examples

Example 1

Input: "aaaaa"

Step	i	Pair	Almost-Equal?	Operations
1	0	a,a	Yes	1
2	2	a,a	Yes	2
End	4	No pair	-	2

Result: 2

Example 2

Input: "abddez"

Step	i	Pair	Difference	Almost-Equal?	Operations
1	0	a,b	1	Yes	1
2	2	d,d	0	Yes	2
3	4	e,z	21	No	2

Result: 2

Example 3

Input: "zyxyxyz"

Step	i	Pair	Difference	Almost-Equal?	Operations
1	0	z,y	1	Yes	1
2	2	x,y	1	Yes	2
3	4	x,y	1	Yes	3
End	6	No pair	-	3

Result: 3

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each character is visited at most once during the scan
Space	O(1)	Only a few variables are used

The algorithm performs a single pass through the string. After processing a pair, the pointer advances by either one or two positions, so the total amount of work is linear in the length of the string. No auxiliary data structures proportional to the input size are required.

Test Cases

sol = Solution()

assert sol.removeAlmostEqualCharacters("aaaaa") == 2      # provided example
assert sol.removeAlmostEqualCharacters("abddez") == 2     # provided example
assert sol.removeAlmostEqualCharacters("zyxyxyz") == 3    # provided example

assert sol.removeAlmostEqualCharacters("a") == 0          # single character
assert sol.removeAlmostEqualCharacters("ab") == 1         # consecutive letters
assert sol.removeAlmostEqualCharacters("aa") == 1         # identical letters
assert sol.removeAlmostEqualCharacters("ac") == 0         # already valid

assert sol.removeAlmostEqualCharacters("abc") == 1        # overlapping violation chain
assert sol.removeAlmostEqualCharacters("abcd") == 2       # every pair invalid

assert sol.removeAlmostEqualCharacters("az") == 0         # far apart letters
assert sol.removeAlmostEqualCharacters("abab") == 2       # repeated consecutive pairs
assert sol.removeAlmostEqualCharacters("aceg") == 0       # no violations

assert sol.removeAlmostEqualCharacters("bbbbbb") == 3     # long identical run
assert sol.removeAlmostEqualCharacters("bcdefg") == 3     # long consecutive chain
assert sol.removeAlmostEqualCharacters("zxwv") == 1       # one invalid pair

Test Summary

Test	Why
"aaaaa"	Long run of identical characters
"abddez"	Multiple separated violations
"zyxyxyz"	Several consecutive violations
"a"	Minimum input size
"ab"	Consecutive alphabet characters
"aa"	Equal characters
"ac"	Already valid pair
"abc"	Overlapping violation chain
"abcd"	Continuous invalid sequence
"az"	Large alphabet gap
"abab"	Repeated bad pairs
"aceg"	No modifications needed
"bbbbbb"	Long identical block
"bcdefg"	Long consecutive chain
"zxwv"	Mixed valid and invalid pairs

Edge Cases

Single Character String

A string of length one contains no adjacent pairs. A common mistake is attempting to access word[i + 1] without checking bounds. The implementation uses the condition i < n - 1, so no out-of-range access occurs and the answer is correctly 0.

Long Run of Identical Characters

Strings such as "aaaaaa" contain many overlapping violations. A naive solution might count every adjacent pair and incorrectly return 5. In reality, changing every other character is sufficient, giving an answer of 3. The greedy skip-by-two strategy correctly handles this situation.

Chain of Consecutive Letters

Strings such as "abcdef" have every adjacent pair differing by exactly one. These violations overlap heavily. Fixing one pair can also help with neighboring pairs. The greedy algorithm accounts for this by counting one operation per disjoint bad pair, producing the optimal answer.

Already Valid String

A string such as "acegik" contains no almost-equal adjacent characters. The scan never finds a bad pair, so operations remains zero. This verifies that the algorithm does not perform unnecessary modifications.