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

String Transforms Into Another String

Number: 1124

Difficulty: Hard

Paid? Yes

Companies: Google

Problem Description

Given two strings, str1 and str2, of the same length, determine whether str1 can be transformed into str2 by performing zero or more conversion operations. In one conversion, you can change all occurrences of one character in str1 to any other lowercase English character. The conversion operations can be performed in any order. The challenge is to decide if such a sequence of conversions exists to obtain exactly str2 from str1.

Key Insights

  • Each character mapping from str1 to str2 must be consistent; one character in str1 always maps to the same character in str2.
  • A bijective mapping is not necessary; multiple characters in str1 can map to the same character in str2.
  • The order of conversions matters. When there is a cycle (e.g., mapping 'a'->'b' and 'b'->'a'), an intermediate unused character might be required to break the cycle.
  • If str2 uses all 26 letters, no temporary character is available to break mapping cycles. In this case, transformation is possible only if str1 is already equal to str2.

Space and Time Complexity

Time Complexity: O(n), where n is the length of the strings, because we traverse the strings to build and check the mapping. Space Complexity: O(1) or O(26), which is constant space, to store the mapping for the 26 lowercase English letters.

Solution

The approach is as follows:

  1. If str1 equals str2, return true immediately.
  2. Build a mapping from each character in str1 to the corresponding character in str2. While creating the mapping, check that each character maps consistently.
  3. Count the number of distinct characters in str2. If this number is 26 and str1 is not already equal to str2, it is impossible to perform the transformation because there is no spare character available as a temporary placeholder.
  4. If the mapping is consistent and there exists at least one character not used in str2 (i.e., distinct characters in str2 is less than 26), the transformation is possible. The important trick is identifying the need for a free character when the target mapping is “full” (i.e., covers all 26 letters). Without a free character, you cannot avoid cycles where a temporary intermediate is necessary.

Code Solutions

# Python solution with line-by-line comments
def canConvert(str1: str, str2: str) -> bool:
    # If both strings are equal, no conversion is needed.
    if str1 == str2:
        return True
    
    # Dictionary to hold the mapping from characters in str1 to characters in str2
    mapping = {}
    
    # Iterate through the characters of both strings simultaneously.
    for c1, c2 in zip(str1, str2):
        # If c1 is already in the mapping, check for consistency.
        if c1 in mapping:
            if mapping[c1] != c2:
                # Found an inconsistent mapping.
                return False
        else:
            mapping[c1] = c2
    
    # Count distinct characters in str2.
    # If str2 uses all 26 letters, then there is no extra character available to break cycles.
    if len(set(str2)) == 26:
        return False
    
    return True

# Example Usage:
#print(canConvert("aabcc", "ccdee"))  # Expected True
#print(canConvert("leetcode", "codeleet"))  # Expected False
← Back to All Questions