2957. Remove Adjacent Almost-Equal Characters

Problem Description

The given problem involves a string word where the objective is to make the minimum number of operations so that no pair of adjacent characters remain that are "almost-equal." A pair of characters are defined as "almost-equal" if either they are the same character or they are adjacent to each other in the alphabet (for example, 'b' and 'c' are adjacent alphabetically).

An operation consists of picking any character in word and changing it to any lowercase English letter of your choice. The task is to find out the least number of such operations required to ensure no "almost-equal" characters are next to each other in the string.

Intuition

To approach this solution efficiently, we utilize a greedy algorithm. The underlying thought process of a greedy approach is to solve a problem by making a sequence of choices, each of which simply looks the best at the moment. It doesn't reconsider choices previously made, even if future actions may create a suboptimal sequence.

Starting from the first character, we traverse the string and consider each adjacent pair of characters. If we find a pair that is almost-equal, we increment our operation counter because we'll need to change one of those characters to remove the almost-equality. We then skip checking the next character because it has been taken care of by this operation. If a pair is not almost-equal, we continue checking with the next character.

By doing this, we count only the minimal number of changes needed without actually performing the substitutions, which aligns precisely with what the problem is asking for—the least number of operations needed, not the resulting string.

Learn more about Greedy and Dynamic Programming patterns.

Solution Approach

The implementation of the solution is straightforward and follows the greedy approach described in the intuition section. The code is written in Python and utilizes basic string manipulation and character comparison by their ASCII values.

Here's a breakdown of the algorithm used in the implementation:

Initialize a variable ans to 0 that will hold the count of necessary operations.
Start iterating over the string word from the second character (index 1 since the string is 0-indexed).
For each character at index i, compare it with the previous character at index i - 1 by calculating the absolute difference of their ASCII values.
If the difference in ASCII value is less than 2, it implies that the characters are either the same or adjacent in the alphabet, and thus "almost-equal".
In such a case, since we need to perform an operation to change either of the "almost-equal" characters, increment ans by 1.
After performing an operation, we make a greedy choice to move 2 indices forward, because we know the next character does not need to be checked as it's already been part of an "almost-equal" pair and would be changed by the operation, thus i is incremented by 2.
If the characters are not "almost-equal," simply move to the next character to continue the check by incrementing i by 1.
Continue this process until all characters have been checked.
Finally, the value of ans provides the minimum number of operations needed to achieve the objective.

The solution doesn't make use of any complex data structures; it only operates on the given string and requires a single pass from left to right, checking the adjacent characters. This approach ensures that the time complexity of the solution is linear, i.e. O(n), where n is the length of the given string. There are no additional memory requirements other than the variables for iteration and counting, making it a constant space solution, O(1).

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Consider the string word = "abaaccdbbd". We want to find the minimum number of operations needed so that no pair of adjacent characters are "almost-equal." Here is how the greedy solution approach is applied step by step:

Initialize ans = 0. No operations have been performed yet.
Start iterating over word from the second character.
Compare characters at index 0 and index 1, 'a' and 'b'. The ASCII difference is 1, they are adjacent alphabetically, so they are "almost-equal."
Increment ans to 1 and skip to comparing characters at index 2 and 3.
Compare characters at index 2 and 3, 'a' and 'a'. They are the same, which means "almost-equal."
Increment ans to 2 and skip to comparing characters at index 4 and 5.
Compare characters at index 4 and 5, 'c' and 'c'. They are the same.
Increment ans to 3 and skip to comparing characters at index 6 and 7.
Compare characters at index 6 and 7, 'd' and 'b'. The ASCII difference is not 1, they are not "almost-equal."
Move to the next characters and compare at index 7 and 8.
Compare characters at index 7 and 8, 'b' and 'b'. They are the same.
Increment ans to 4. Since we are at the penultimate character, the algorithm ends here.
The minimum number of operations needed is the final value of ans, which is 4.

The greedy approach only requires us to check each character once and move on based on the "almost-equal" condition, minimizing the number of operations effectively.

Solution Implementation

1class Solution:
2    def removeAlmostEqualCharacters(self, word: str) -> int:
3        # Initialize a count for almost equal character pairs.
4        count = 0
5      
6        # Initialize an index variable for iterating through the string.
7        index = 1
8      
9        # Get the length of the word for boundary checks.
10        length_of_word = len(word)
11      
12        # Loop through the word.
13        while index < length_of_word:
14            # Check if the absolute difference between the ASCII values of adjacent
15            # characters is less than 2 (which means the characters are almost equal).
16            if abs(ord(word[index]) - ord(word[index - 1])) < 2:
17                # If so, increment the count since the pair is considered as removed.
18                count += 1
19              
20                # Skip the next character as the pair has been "removed".
21                index += 2
22            else:
23                # Move to the next character for comparison.
24                index += 1
25      
26        # Return the total count of almost equal character pairs removed.
27        return count
28

1class Solution {
2    // Method to remove "almost equal" characters from the given string 'word'
3    public int removeAlmostEqualCharacters(String word) {
4        int removalCount = 0; // This will store the count of the removals made
5        int wordLength = word.length(); // Store the length of the word
6
7        // Loop through the characters of the word while skipping one character after each removal
8        for (int i = 1; i < wordLength; ++i) {
9            // Check if the current character and the previous one are "almost equal"
10            // "Almost equal" means their unicode difference is less than 2
11            if (Math.abs(word.charAt(i) - word.charAt(i - 1)) < 2) {
12                removalCount++; // Increment the count of near removals
13                i++; // Skip the next character since we removed a pair
14            }
15        }
16
17        // Return the total number of removals made
18        return removalCount;
19    }
20}
21

1class Solution {
2public:
3    int removeAlmostEqualCharacters(string word) {
4        // 'count' variable is used to track the number of removals
5        int count = 0;
6        // Calculate the size of the string 'word'
7        int wordSize = word.size();
8      
9        // Loop through the string starting from the second character
10        for (int i = 1; i < wordSize; ++i) {
11            // Check if the current and previous characters are almost equal (difference < 2)
12            if (abs(word[i] - word[i - 1]) < 2) {
13                // Increment count since these two characters will be removed
14                ++count;
15                // Skip the next character as it has been considered in the almost equal pair
16                ++i;
17            }
18        }
19        // Return the total number of removals
20        return count;
21    }
22};
23

1// This function removes adjacent pairs of characters from a given word if their
2// Unicode values differ by less than 2. It returns the number of character pairs removed.
3function removeAlmostEqualCharacters(word: string): number {
4    // Initialize the count of removed character pairs
5    let removedCount = 0;
6  
7    // Loop through the string, starting from the second character
8    for (let index = 1; index < word.length; ++index) {
9        // Calculate the absolute difference between the current character and the previous one
10        const charCodeDifference = Math.abs(word.charCodeAt(index) - word.charCodeAt(index - 1));
11      
12        // If the difference is less than 2, a pair is almost equal and should be removed
13        if (charCodeDifference < 2) {
14            // Increment the count of removed character pairs
15            ++removedCount;
16            // Skip the next character to only remove pairs
17            ++index;
18        }
19    }
20  
21    // Return the count of removed character pairs
22    return removedCount;
23}
24

Time and Space Complexity

The time complexity of the given code is O(n) where n is the length of the string word. This is because the loop runs for at most n steps as it increments by either 1 or 2 in each iteration, ensuring that each character is visited no more than once.

The space complexity of the code is O(1). It only uses a fixed number of extra variables (like ans, i, and n) that do not depend on the size of the input string, hence it uses constant additional space.

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

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

Which type of traversal does breadth first search do?

Pre-order traversal

Post-order traversal

In-order traversal

Level-order traversal

I don’t know