We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Remove Adjacent Almost-Equal Characters

Number: 3230

Difficulty: Medium

Paid? No

Companies: Salesforce

Problem Description

You are given a 0-indexed string word consisting only of lowercase English letters. In one operation, you can change any letter in the string to any lowercase English letter. Two characters are defined as almost-equal if they are equal or adjacent in the alphabet (for example, 'a' and 'b' or 'b' and 'a'). The goal is to determine the minimum number of operations required to transform word into a string where no two adjacent characters are almost-equal.

Key Insights

  • The "almost-equal" condition is defined as two characters being the same or consecutive in the alphabet.
  • We need to ensure that after operations no two adjacent characters are almost-equal.
  • A dynamic programming approach can be used where we consider, for each position, all possible choices of characters.
  • The state dp[i][c] represents the minimum operations needed for the substring ending at index i if the letter at position i is changed to character c.
  • Transition: For each position, iterate over all possible previous letters ensuring the pair (prev, cur) is not almost-equal, and update the cost accordingly.

Space and Time Complexity

Time Complexity: O(n * 26 * 26) where n is the length of the word. Space Complexity: O(n * 26) for storing the DP table.

Solution

We will use a dynamic programming approach. For each position in the string, we compute the minimum operations required if we change the character at that position to any letter from 'a' to 'z'. The transition ensures that the chosen letter for the current position does not form an almost-equal pair with the chosen letter at the previous position. The key data structure is a 2D DP array where dp[i][c] holds the minimum operations for the substring[0..i] when word[i] is set to character c. The cost per position is 0 if the chosen letter is already there, or 1 if we need to change it.

Code Solutions

# Python solution with line-by-line comments

def minOperations(word: str) -> int:
    n = len(word)
    # Create a DP table with dimensions [n][26] initialized to a large number
    dp = [[float('inf')] * 26 for _ in range(n)]
    
    # Base case: for the first character, cost is 0 if we keep it, else 1
    for c in range(26):
        dp[0][c] = 0 if c == ord(word[0]) - ord('a') else 1
    
    # Helper function to check if two characters are almost-equal
    def is_almost_equal(p, c):
        # p and c are integer indices corresponding to characters
        return p == c or abs(p - c) == 1
    
    # Fill DP table for each position from 1 to n-1
    for i in range(1, n):
        for cur in range(26):
            # cost to set current letter to 'cur'
            cost = 0 if cur == ord(word[i]) - ord('a') else 1
            for prev in range(26):
                # Only consider previous letter 'prev' if it does not conflict with current letter 'cur'
                if not is_almost_equal(prev, cur):
                    dp[i][cur] = min(dp[i][cur], dp[i-1][prev] + cost)
    
    # The answer is the minimal value in the last row of DP table
    return min(dp[n-1])

# Example usage:
print(minOperations("aaaaa"))  # Expected output: 2
print(minOperations("abddez"))  # Expected output: 2
print(minOperations("zyxyxyz"))  # Expected output: 3
← Back to All Questions