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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Equalize Strings by Adding or Removing Characters at Ends

Number: 3441

Difficulty: Medium

Paid? Yes

Companies: Salesforce

Problem Description

Given two strings initial and target, you can perform operations that only add or remove a single character at either the beginning or the end of the string initial. The task is to determine the minimum number of operations required to transform initial into target.

Key Insights

  • You can only remove characters from the beginning or the end of initial, meaning the remaining preserved part must be a contiguous substring.
  • Similarly, you can only add characters at the beginning or the end; hence the preserved substring must align with a contiguous substring of target.
  • The optimal strategy is to preserve the longest common contiguous substring between initial and target.
  • The answer is the sum of the characters removed from initial and the characters added to get to target.
  • The formula becomes: operations = (initial.length - commonSubstringLength) + (target.length - commonSubstringLength).

Space and Time Complexity

Time Complexity: O(n * m) where n = initial.length and m = target.length
Space Complexity: O(1) extra space

Solution

The solution iterates over all possible contiguous substrings of initial and checks if they appear in target. The length of the longest such substring is saved as maxLen. The minimum operations required is then computed using the formula: (initial.length + target.length - 2 * maxLen). This works because we are effectively removing characters from both ends of initial (to isolate the common substring) and then adding the remaining characters to form target. This idea leverages a simple brute-force search which is acceptable given the constraint sizes.

Code Solutions

# Python solution with detailed comments
def minOperations(initial: str, target: str) -> int:
    n = len(initial)
    m = len(target)
    max_common_length = 0  # stores the maximum length of a contiguous substring that is in both strings

    # iterate over all starting indices in initial
    for i in range(n):
        # iterate over all ending indices for substring starting at i
        for j in range(i, n):
            # define the current substring of initial
            substring = initial[i:j+1]
            # check if the substring exists in target
            if substring in target:
                current_length = j - i + 1
                if current_length > max_common_length:
                    max_common_length = current_length
    # calculate the required operations based on the longest common contiguous substring
    return (n - max_common_length) + (m - max_common_length)

# Example usage and test cases
print(minOperations("abcde", "cdef"))  # Expected output: 3
print(minOperations("axxy", "yabx"))   # Expected output: 6
print(minOperations("xyz", "xyz"))     # Expected output: 0
← Back to All Questions