Remove Adjacent Almost-Equal Characters

Medium

Asked by:

2 views

Topics:

StringsGreedy Algorithms

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.

Return the minimum number of operations needed to remove all adjacent almost-equal characters from word.

Two characters a and b are almost-equal if a == b or a and b are adjacent in the alphabet.

Example 1:

Input: word = "aaaaa"
Output: 2
Explanation: We can change word into "acaca" which does not have any adjacent almost-equal characters.
It can be shown that the minimum number of operations needed to remove all adjacent almost-equal characters from word is 2.

Example 2:

Input: word = "abddez"
Output: 2
Explanation: We can change word into "ybdoez" which does not have any adjacent almost-equal characters.
It can be shown that the minimum number of operations needed to remove all adjacent almost-equal characters from word is 2.

Example 3:

Input: word = "zyxyxyz"
Output: 3
Explanation: We can change word into "zaxaxaz" which does not have any adjacent almost-equal characters. 
It can be shown that the minimum number of operations needed to remove all adjacent almost-equal characters from word is 3.

Constraints:

1 <= word.length <= 100
word consists only of lowercase English letters.

Try coding it in LeetCode

Remove Adjacent Almost-Equal Characters

Medium

Asked by:

2 views

Topics:

StringsGreedy Algorithms

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.

Return the minimum number of operations needed to remove all adjacent almost-equal characters from word.

Two characters a and b are almost-equal if a == b or a and b are adjacent in the alphabet.

Example 1:

Input: word = "aaaaa"
Output: 2
Explanation: We can change word into "acaca" which does not have any adjacent almost-equal characters.
It can be shown that the minimum number of operations needed to remove all adjacent almost-equal characters from word is 2.

Example 2:

Input: word = "abddez"
Output: 2
Explanation: We can change word into "ybdoez" which does not have any adjacent almost-equal characters.
It can be shown that the minimum number of operations needed to remove all adjacent almost-equal characters from word is 2.

Example 3:

Input: word = "zyxyxyz"
Output: 3
Explanation: We can change word into "zaxaxaz" which does not have any adjacent almost-equal characters. 
It can be shown that the minimum number of operations needed to remove all adjacent almost-equal characters from word is 3.

Constraints:

1 <= word.length <= 100
word consists only of lowercase English letters.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the maximum possible length of the input string `s`?
Can the input string `s` be empty or null?
Are all characters in the string ASCII characters, or could there be Unicode characters?
If multiple solutions exist (different removal sequences leading to the same minimum length), is any valid solution acceptable?
Should I return the minimum number of *removed* characters, or the minimum length of the *remaining* string?

Brute Force Solution

Approach

The brute force strategy for this problem is to check every possible combination of character removals. We'll look at each pair of adjacent characters and, if they are 'almost equal', we'll explore what happens if we remove the first one, the second one, or neither.

Here's how the algorithm would work step-by-step:

Start with the original string.
Look at the first two characters. Check if they are 'almost equal'.
If they are, make two new strings: one where you remove the first character, and another where you remove the second character.
If they are not 'almost equal', keep the string as is.
Now, for each of the new strings you made (or the original string if you didn't remove anything), repeat the process by looking at the next pair of adjacent characters.
Keep going until you've examined all pairs of adjacent characters in all the strings you've created.
At the end, you'll have a list of strings, each representing a different set of removals. Choose the shortest one from this list, as that represents the fewest characters remaining after removals.

Code Implementation

def remove_adjacent_almost_equal_characters_brute_force(input_string):
    shortest_string = input_string

    def find_almost_equal_adjacent_indices(current_string):
        indices = []
        for index in range(len(current_string) - 1):
            if abs(ord(current_string[index]) - ord(current_string[index + 1])) == 1:
                indices.append(index)
        return indices

    def solve(current_string):
        nonlocal shortest_string

        adjacent_indices = find_almost_equal_adjacent_indices(current_string)

        if not adjacent_indices:
            # No almost-equal chars exist, check if shortest.
            if len(current_string) < len(shortest_string):
                shortest_string = current_string
            return

        for index_to_remove in adjacent_indices:
            # Explore removing each possible char.
            new_string = current_string[:index_to_remove] + current_string[index_to_remove+1:]

            solve(new_string)

    solve(input_string)
    return shortest_string

Big(O) Analysis

Time Complexity

O(3^n) – The brute force approach explores all possible combinations of removing almost-equal adjacent characters. For each pair of adjacent characters, there are three possibilities: remove the first, remove the second, or remove neither. If the input string has n characters, then there are approximately n/2 pairs of adjacent characters that could be 'almost equal'. This leads to a branching factor of 3 for approximately n/2 levels, resulting in approximately 3^(n/2) possibilities explored. Hence, the time complexity is O(3^n) since constants are ignored in Big O notation.

Space Complexity

O(3^N) – The provided brute force solution explores all possible combinations of removing adjacent 'almost equal' characters. For each pair of almost equal characters, the algorithm branches into three possibilities: removing the first character, removing the second character, or removing neither. In the worst-case scenario, every adjacent pair is almost equal, leading to a branching factor of 3 at each position. Therefore, the number of strings generated can grow exponentially with the input size N (where N is the length of the string), specifically as 3^N. Since we store all these generated strings, the auxiliary space complexity is O(3^N).

Optimal Solution

Approach

The core idea is to go through the text character by character, deciding at each step whether to keep a character or remove it. The trick is to remove a character only if it is almost equal to the character immediately following it.

Here's how the algorithm would work step-by-step:

Start at the beginning of the text.
Look at the current character and the next character.
If the current character and the next character are 'almost equal' (differ by at most one), then remove the character that comes first.
However, if the next character is also 'almost equal' to the character that comes after it, then you remove the latter of the first pair.
If the characters are not 'almost equal', keep the current character and move on to the next character.
Repeat this process until you reach the end of the text.
The remaining characters will be the text with adjacent 'almost equal' characters removed.

Code Implementation

def remove_adjacent_almost_equal_characters(input_string):
    result_string = ""
    
    for char in input_string:
        if not result_string:
            # The first character is always safe to add.
            result_string += char

        else:
            last_char_in_result = result_string[-1]
            
            # Check if the current char is 'almost equal' to the last one.
            if abs(ord(char) - ord(last_char_in_result)) != 1:
                # Keep the current character if it's not almost equal.
                result_string += char

    return result_string

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the string once, examining each character and its adjacent character. For each character, it performs a constant-time comparison to determine if the characters are almost equal and decides whether to remove the current character. Since each character is visited and processed only once, the time complexity is directly proportional to the length of the input string, n.

Space Complexity

O(N) – The algorithm constructs a new string or list of characters to store the result as it iterates through the input text of length N. In the worst-case scenario, where no adjacent characters are 'almost equal', every character from the original text will be added to this new data structure. Therefore, the space required to store the result grows linearly with the input size N, leading to a space complexity of O(N).

Edge Cases

Case	How to Handle
Empty string	Return 0 since there are no characters to remove.
String with a single character	Return 0 since there are no adjacent characters.
String with two almost-equal characters	Return 1 since one of them should be removed.
String with two non-almost-equal characters	Return 0 since no removal is required.
String with all almost-equal characters (e.g., 'abcba')	The algorithm should greedily remove characters until no adjacent almost-equal characters remain, leading to potentially significant removals.
Long string where the solution requires many removals, testing performance.	The solution should be optimized to avoid quadratic or exponential time complexity.
String with ASCII values at the boundaries (0 and 255) that might cause integer under/overflow during subtraction	Use the absolute difference function to ensure correct comparison regardless of the order and to prevent under/overflow.
A string like 'aaaaaa' where removing adjacent characters does not change the number of 'a' left at the end.	The code must correctly identify that removing 'aa' removes one character effectively and doesn't get stuck at the beginning.