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.
What is the running time of the following code?
1int sqrt(int n) { 2 for (int guess = 1; guess * guess <= n; guess++) { 3 if (guess * guess == n) { 4 return guess; 5 } 6 } 7 return -1; 8}
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
ansto0that will hold the count of necessary operations. - Start iterating over the string
wordfrom the second character (index1since the string is 0-indexed). - For each character at index
i, compare it with the previous character at indexi - 1by 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
ansby1. - After performing an operation, we make a greedy choice to move
2indices 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, thusiis incremented by2. - If the characters are not "almost-equal," simply move to the next character to continue the check by incrementing
iby1. - Continue this process until all characters have been checked.
- Finally, the value of
ansprovides 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).
What are the two properties the problem needs to have for dynamic programming to be applicable? (Select 2)
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
wordfrom 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
ansto 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
ansto 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
ansto 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
ansto 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
281class 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}
211class 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};
231// 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}
24What is the space complexity of the following code?
1int sum(int n) {
2 if (n <= 0) {
3 return 0;
4 }
5 return n + sum(n - 1);
6}
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.
Which data structure is used to implement priority queue?
Recommended Readings
Greedy Introduction iframe width 560 height 315 src https www youtube com embed WTslqPbj7I title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture web share allowfullscreen iframe When do we use greedy Greedy algorithms tend to solve optimization problems Typically they will ask you
What is Dynamic Programming Prerequisite DFS problems dfs_intro Backtracking problems backtracking Memoization problems memoization_intro Pruning problems backtracking_pruning Dynamic programming is an algorithmic optimization technique that breaks down a complicated problem into smaller overlapping sub problems in a recursive manner and uses solutions to the sub problems to construct a solution
Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture
Got a question? Ask the Teaching Assistant anything you don't understand.
Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.