Jobs

Interviews

Discussions

String Transforms Into Another String

Hard

Asked by:

21 views

Topics:

StringsArraysGreedy Algorithms

Given two strings str1 and str2 of the same length, determine whether you can transform str1 into str2 by doing zero or more conversions.

In one conversion you can convert all occurrences of one character in str1 to any other lowercase English character.

Return true if and only if you can transform str1 into str2.

Example 1:

Input: str1 = "aabcc", str2 = "ccbbc"
Output: true
Explanation: Convert 'a' to 'c', then convert 'b' to 'b'.'

Example 2:

Input: str1 = "leetcode", str2 = "codeleet"
Output: false
Explanation: There is no way to transform str1 to str2.

Constraints:

1 <= str1.length <= 10⁴
str2.length == str1.length
Both str1 and str2 contain only lowercase English letters.

Try coding it in LeetCode

String Transforms Into Another String

Hard

Asked by:

21 views

Topics:

StringsArraysGreedy Algorithms

Given two strings str1 and str2 of the same length, determine whether you can transform str1 into str2 by doing zero or more conversions.

In one conversion you can convert all occurrences of one character in str1 to any other lowercase English character.

Return true if and only if you can transform str1 into str2.

Example 1:

Input: str1 = "aabcc", str2 = "ccbbc"
Output: true
Explanation: Convert 'a' to 'c', then convert 'b' to 'b'.'

Example 2:

Input: str1 = "leetcode", str2 = "codeleet"
Output: false
Explanation: There is no way to transform str1 to str2.

Constraints:

1 <= str1.length <= 10⁴
str2.length == str1.length
Both str1 and str2 contain only lowercase English letters.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can the input strings `str1` and `str2` be empty or null?
Are `str1` and `str2` guaranteed to be of the same length?
What characters can the strings contain (e.g., only lowercase letters, ASCII characters, Unicode characters)?
If it's impossible to transform `str1` into `str2`, what should I return (e.g., `false`, throw an exception)?
If `str1` and `str2` are already equal, should I return `true` or `false`?

Brute Force Solution

Approach

The brute force approach to transforming one string to another involves exploring all possible character mappings. We try every conceivable way to replace characters in the first string to see if we can get the second string. If a match exists, it means the transformation is possible.

Here's how the algorithm would work step-by-step:

Start by trying to map the first unique character in the first string to every possible character in the second string.
For each of those mappings, try to map the next unique character in the first string (if any) to every possible character in the second string, ensuring no conflict with previous mappings.
Continue this process for all unique characters in the first string, building up a full potential character mapping.
Once you have a complete mapping, check if applying this mapping to the first string results in the second string.
If it does, then you've found a valid transformation and can say it's possible.
If you've exhausted all possible mappings without finding a match, then the transformation is not possible.

Code Implementation

def can_transform_brute_force(string1, string2):
    if len(string1) != len(string2):
        return False

    unique_characters = []
    for character in string1:
        if character not in unique_characters:
            unique_characters.append(character)

    def check_mapping(index, current_mapping):
        if index == len(unique_characters):
            transformed_string = "".join([current_mapping.get(character, character) for character in string1])
            return transformed_string == string2

        character_to_map = unique_characters[index]
        
        # Iterate through possible mappings
        for replacement_character in set(string2):
            
            # Check for conflicts in our mapping
            if replacement_character in current_mapping.values() and character_to_map not in current_mapping:
                continue

            new_mapping = current_mapping.copy()
            new_mapping[character_to_map] = replacement_character
            
            if check_mapping(index + 1, new_mapping):
                return True

        return False

    # Start the recursion with an empty mapping
    return check_mapping(0, {})

Big(O) Analysis

Time Complexity

O(26^26) – The brute force approach explores all possible character mappings. Since there are at most 26 unique characters in the first string, for each unique character, we attempt to map it to every character in the second string. In the worst-case scenario, where all 26 characters are unique in the first string, we have 26 choices for the first character, 26 choices for the second, and so on, leading to 26 multiplied by itself 26 times, or 26^26. Once a mapping is created, we must iterate through the string (length n) to test this mapping, which is dwarfed by the possible mapping cost. Therefore, the time complexity is approximately O(26^26) since it explores all possible mappings.

Space Complexity

O(1) – The brute force approach, as described, primarily explores different character mappings without explicitly storing all of them simultaneously. The algorithm's memory usage consists mainly of storing temporary variables, such as individual character mappings being tested, and potentially a recursion stack if implemented recursively. The maximum number of unique characters in the input string is limited (e.g., by the character set, such as ASCII), which means the size of the mapping is also bounded by a constant. Therefore, the auxiliary space is independent of the input string's length N and remains constant.

Optimal Solution

Approach

The key insight is to realize that if two characters in the first string map to the same character in the second string, and there's a cycle, a transformation is impossible. Also, if the first string contains unique characters, we need a 'spare' character in the first string. We will focus on checking for cycles and the spare character.

Here's how the algorithm would work step-by-step:

First, check if the two strings have different lengths. If they do, it's impossible to transform one into the other.
Create a way to remember which character in the first string should be changed to which character in the second string.
Now, check if there is a situation where two different characters in the first string need to be changed to the same character in the second string. If this is true, it is likely impossible, unless there is a spare character.
Also, if the first string only contains unique characters, check if there is a spare character in the first string, that isn't already used in the mapping.
Finally, if the string's characters are all unique, consider the scenario where the second string has fewer characters than the first string. This could be a success case.

Code Implementation

def can_convert_string(string1, string2):
    if len(string1) != len(string2):
        return False

    mapping = {}

    # Check for conflicting mappings; transformation impossible
    for i in range(len(string1)):
        char1 = string1[i]
        char2 = string2[i]
        if char1 not in mapping:
            mapping[char1] = char2
        elif mapping[char1] != char2:
            return False

    # Need a spare character if all chars in string1 are unique
    if len(set(string1)) == 26 and len(set(string2)) == 26:
        return False

    return True

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the strings of length n once to build a character mapping. It then iterates through the mapping to check for conflicts which is also bounded by n. Checking for the unique character count involves iterating through the string once. Therefore, the overall time complexity is dominated by these linear traversals, resulting in O(n).

Space Complexity

O(1) – The algorithm uses a fixed-size data structure to remember the character mapping (a dictionary or hash map). The size of this mapping is at most the size of the character set which is constant. No other data structures scale with the input size, so the auxiliary space remains constant regardless of the input string length N.

Edge Cases

Case	How to Handle
Null or empty strings s1 or s2	Return true if both are null/empty, false if only one is, and proceed otherwise.
Strings s1 and s2 have different lengths	Return false immediately, as no transformation can make them equal if lengths differ.
s1 and s2 are identical	Return true immediately because an empty transformation is sufficient.
s1 contains duplicate characters, but s2 doesn't	The mapping must be one-to-one, so if duplicates in s1 map to different characters in s2, return false.
A character in s1 maps to a different character at different positions	The mapping must be consistent; if s1[i] maps to different s2[i] for different i, return false.
A character in s2 is mapped to by two different characters in s1	If a character in s2 appears mapped by two different characters in s1, we can not change s1 to s2, return false.
s1 contains all same characters and s2 contains all same characters, but the characters are different	If s1 and s2 have distinct characters, they can be transformed, however, if there is only a single unique character it is impossible to transform.
s2 is composed of only a single, repeated character, while s1 contains other characters	If s2 consists of the same character but it also exists in s1, the function should still return false since a character needs to be swapped in a cyclical way.

Null or empty strings s1 or s2

How to Handle:

Return true if both are null/empty, false if only one is, and proceed otherwise.

Strings s1 and s2 have different lengths

How to Handle:

Return false immediately, as no transformation can make them equal if lengths differ.

s1 and s2 are identical

How to Handle:

Return true immediately because an empty transformation is sufficient.

s1 contains duplicate characters, but s2 doesn't

How to Handle:

The mapping must be one-to-one, so if duplicates in s1 map to different characters in s2, return false.

A character in s1 maps to a different character at different positions

How to Handle:

The mapping must be consistent; if s1[i] maps to different s2[i] for different i, return false.

A character in s2 is mapped to by two different characters in s1

How to Handle:

If a character in s2 appears mapped by two different characters in s1, we can not change s1 to s2, return false.

s1 contains all same characters and s2 contains all same characters, but the characters are different

How to Handle:

If s1 and s2 have distinct characters, they can be transformed, however, if there is only a single unique character it is impossible to transform.

s2 is composed of only a single, repeated character, while s1 contains other characters

How to Handle:

If s2 consists of the same character but it also exists in s1, the function should still return false since a character needs to be swapped in a cyclical way.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can the input strings `str1` and `str2` be empty or null?
Are `str1` and `str2` guaranteed to be of the same length?
What characters can the strings contain (e.g., only lowercase letters, ASCII characters, Unicode characters)?
If it's impossible to transform `str1` into `str2`, what should I return (e.g., `false`, throw an exception)?
If `str1` and `str2` are already equal, should I return `true` or `false`?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Start by trying to map the first unique character in the first string to every possible character in the second string.
For each of those mappings, try to map the next unique character in the first string (if any) to every possible character in the second string, ensuring no conflict with previous mappings.
Continue this process for all unique characters in the first string, building up a full potential character mapping.
Once you have a complete mapping, check if applying this mapping to the first string results in the second string.
If it does, then you've found a valid transformation and can say it's possible.
If you've exhausted all possible mappings without finding a match, then the transformation is not possible.

Code Implementation

def can_transform_brute_force(string1, string2):
    if len(string1) != len(string2):
        return False

    unique_characters = []
    for character in string1:
        if character not in unique_characters:
            unique_characters.append(character)

    def check_mapping(index, current_mapping):
        if index == len(unique_characters):
            transformed_string = "".join([current_mapping.get(character, character) for character in string1])
            return transformed_string == string2

        character_to_map = unique_characters[index]
        
        # Iterate through possible mappings
        for replacement_character in set(string2):
            
            # Check for conflicts in our mapping
            if replacement_character in current_mapping.values() and character_to_map not in current_mapping:
                continue

            new_mapping = current_mapping.copy()
            new_mapping[character_to_map] = replacement_character
            
            if check_mapping(index + 1, new_mapping):
                return True

        return False

    # Start the recursion with an empty mapping
    return check_mapping(0, {})

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

First, check if the two strings have different lengths. If they do, it's impossible to transform one into the other.
Create a way to remember which character in the first string should be changed to which character in the second string.
Now, check if there is a situation where two different characters in the first string need to be changed to the same character in the second string. If this is true, it is likely impossible, unless there is a spare character.
Also, if the first string only contains unique characters, check if there is a spare character in the first string, that isn't already used in the mapping.
Finally, if the string's characters are all unique, consider the scenario where the second string has fewer characters than the first string. This could be a success case.

Code Implementation

def can_convert_string(string1, string2):
    if len(string1) != len(string2):
        return False

    mapping = {}

    # Check for conflicting mappings; transformation impossible
    for i in range(len(string1)):
        char1 = string1[i]
        char2 = string2[i]
        if char1 not in mapping:
            mapping[char1] = char2
        elif mapping[char1] != char2:
            return False

    # Need a spare character if all chars in string1 are unique
    if len(set(string1)) == 26 and len(set(string2)) == 26:
        return False

    return True

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty strings s1 or s2	Return true if both are null/empty, false if only one is, and proceed otherwise.
Strings s1 and s2 have different lengths	Return false immediately, as no transformation can make them equal if lengths differ.
s1 and s2 are identical	Return true immediately because an empty transformation is sufficient.
s1 contains duplicate characters, but s2 doesn't	The mapping must be one-to-one, so if duplicates in s1 map to different characters in s2, return false.
A character in s1 maps to a different character at different positions	The mapping must be consistent; if s1[i] maps to different s2[i] for different i, return false.
A character in s2 is mapped to by two different characters in s1	If a character in s2 appears mapped by two different characters in s1, we can not change s1 to s2, return false.
s1 contains all same characters and s2 contains all same characters, but the characters are different	If s1 and s2 have distinct characters, they can be transformed, however, if there is only a single unique character it is impossible to transform.
s2 is composed of only a single, repeated character, while s1 contains other characters	If s2 consists of the same character but it also exists in s1, the function should still return false since a character needs to be swapped in a cyclical way.

Null or empty strings s1 or s2

How to Handle:

Return true if both are null/empty, false if only one is, and proceed otherwise.

Strings s1 and s2 have different lengths

How to Handle:

Return false immediately, as no transformation can make them equal if lengths differ.

s1 and s2 are identical

How to Handle:

Return true immediately because an empty transformation is sufficient.

s1 contains duplicate characters, but s2 doesn't

How to Handle:

The mapping must be one-to-one, so if duplicates in s1 map to different characters in s2, return false.

A character in s1 maps to a different character at different positions

How to Handle:

The mapping must be consistent; if s1[i] maps to different s2[i] for different i, return false.

A character in s2 is mapped to by two different characters in s1

How to Handle:

If a character in s2 appears mapped by two different characters in s1, we can not change s1 to s2, return false.

s1 contains all same characters and s2 contains all same characters, but the characters are different

How to Handle:

If s1 and s2 have distinct characters, they can be transformed, however, if there is only a single unique character it is impossible to transform.

s2 is composed of only a single, repeated character, while s1 contains other characters

How to Handle:

If s2 consists of the same character but it also exists in s1, the function should still return false since a character needs to be swapped in a cyclical way.