How hard is LeetCode 2957. Remove Adjacent Almost-Equal Characters?

LeetCode 2957. Remove Adjacent Almost-Equal Characters is rated Medium on LeetCode.

What is the time complexity of LeetCode 2957. Remove Adjacent Almost-Equal Characters?

The Python solution on this page runs in O(n), where n is the length of the string `word`.

What is the space complexity of LeetCode 2957. Remove Adjacent Almost-Equal Characters?

The Python solution on this page uses O(1) auxiliary space.

What topics does LeetCode 2957. Remove Adjacent Almost-Equal Characters cover?

LeetCode 2957. Remove Adjacent Almost-Equal Characters is tagged Greedy, String and Dynamic Programming on LeetCode.

Remove Adjacent Almost-Equal Characters — LeetCode 2957 Python Solution

MediumGreedyStringDynamic Programming

Problem: #2957
Pattern: Greedy
Reading time: 2 min
Source: leetcode.com

The problem

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.

Example

Input: word = "aaaaa"
Output: 2
Explanation: We can change word into "acaca" which does not have any adjacent almost-equal characters.

Python solution

Python

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

Complexity

Measure	Complexity
Time	O(n), where n is the length of the string `word`
Space	O(1) auxiliary

Pattern: Greedy

Take the locally best option every time — when you can prove that never costs you later. LeetCode 2957. Remove Adjacent Almost-Equal Characters is filed here because LeetCode tags it Greedy, which is the vocabulary this hub collects.

The greedy guide has the Python template for the pattern and the 346 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 2957. Remove Adjacent Almost-Equal Characters?: LeetCode 2957. Remove Adjacent Almost-Equal Characters is rated Medium on LeetCode.
What is the time complexity of LeetCode 2957. Remove Adjacent Almost-Equal Characters?: The Python solution on this page runs in O(n), where n is the length of the string `word`.
What is the space complexity of LeetCode 2957. Remove Adjacent Almost-Equal Characters?: The Python solution on this page uses O(1) auxiliary space.
What topics does LeetCode 2957. Remove Adjacent Almost-Equal Characters cover?: LeetCode 2957. Remove Adjacent Almost-Equal Characters is tagged Greedy, String and Dynamic Programming on LeetCode.