Remove Adjacent Almost-Equal Characters
MedPrompt
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 <= 100wordconsists only of lowercase English letters.
Approaches
2 approaches with complexity analysis and trade-offs.
This approach uses dynamic programming to solve the problem by building up a solution from smaller subproblems. We define a state dp[i][char] representing the minimum operations for the prefix of the string of length i+1, ending with a specific character char. By iterating through the string and all possible characters, we can compute the optimal solution for the entire string.
Algorithm
string
Walkthrough
We can define dp[i][j] as the minimum number of operations required for the prefix word[0...i] such that the character at index i is modified to be the j-th letter of the alphabet ('a' + j).
Algorithm:
- State Definition:
dp[i][j]= minimum operations forword[0...i]withword[i]being'a' + j. - Base Case (i=0): For the first character,
dp[0][j]is1ifword.charAt(0)is not'a' + j(one change is needed), and0otherwise. - Recurrence Relation (i > 0): To compute
dp[i][j], we consider the cost of changingword.charAt(i)to'a' + j, and add it to the minimum cost from the previous statedp[i-1]. The character ati-1, let's say'a' + k, must not be almost-equal to'a' + j. This meansabs(j - k) > 1.dp[i][j] = (word.charAt(i) == 'a' + j ? 0 : 1) + min(dp[i-1][k])for allksuch thatabs(j - k) > 1. - Final Answer: The result is the minimum value in the last row of our DP table,
min(dp[n-1][j])for alljfrom 0 to 25.
This can be implemented with a 2D DP table. The complexity can be improved by optimizing the search for min(dp[i-1][k]) and by reducing the space to O(C) since dp[i] only depends on dp[i-1].
Here is the space-optimized DP implementation:
class Solution { public int removeAlmostEqualCharacters(String word) { int n = word.length(); // dp[j] will store the min operations for the current prefix ending with 'a'+j int[] dp = new int[26]; // Base case: i = 0 for (int j = 0; j < 26; j++) { dp[j] = (word.charAt(0) == (char)('a' + j)) ? 0 : 1; } // Fill DP table for i > 0 for (int i = 1; i < n; i++) { int[] nextDp = new int[26]; // To optimize finding min(dp[k]) where abs(j-k) > 1, we precompute prefix/suffix mins int[] prefixMin = new int[26]; int[] suffixMin = new int[26]; prefixMin[0] = dp[0]; for (int k = 1; k < 26; k++) { prefixMin[k] = Math.min(prefixMin[k - 1], dp[k]); } suffixMin[25] = dp[25]; for (int k = 24; k >= 0; k--) { suffixMin[k] = Math.min(suffixMin[k + 1], dp[k]); } for (int j = 0; j < 26; j++) { int cost = (word.charAt(i) == (char)('a' + j)) ? 0 : 1; int minPrevDp = Integer.MAX_VALUE; if (j - 2 >= 0) { minPrevDp = Math.min(minPrevDp, prefixMin[j - 2]); } if (j + 2 < 26) { minPrevDp = Math.min(minPrevDp, suffixMin[j + 2]); } nextDp[j] = cost + minPrevDp; } dp = nextDp; } // Find the minimum in the final DP array int minOps = Integer.MAX_VALUE; for (int val : dp) { minOps = Math.min(minOps, val); } return minOps; }}Complexity
Time
O(N * C^2), where N is the string length and C is the alphabet size (26). With precomputation of prefix/suffix minimums, this can be optimized to O(N * C).
Space
O(N * C) for a naive implementation, where N is the string length and C is the alphabet size (26). This can be optimized to O(C) because each state only depends on the previous state.
Trade-offs
Pros
Guaranteed to find the optimal solution by exhaustively checking all valid states.
It is a standard and systematic way to solve optimization problems on sequences.
Cons
Higher time and space complexity compared to a greedy approach.
The implementation is more complex, involving a 2D array or two arrays for state management.
Solutions
Solution
class Solution {public int removeAlmostEqualCharacters(String word) { int ans = 0, n = word.length(); for (int i = 1; i < n; ++i) { if (Math.abs(word.charAt(i) - word.charAt(i - 1)) < 2) { ++ans; ++i; } } return ans; }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.