String Transforms Into Another String - Practice Coding Problems

String Transforms Into Another String - Problem

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.

Input & Output

Example 1 — Simple Mapping

$ Input: str1 = "aab", str2 = "xxy"

› Output: true

💡 Note: We can convert 'a' to 'x' and 'b' to 'y': aab → xab → xxy. Each character in str1 maps consistently to one character in str2.

Example 2 — Conflicting Mapping

$ Input: str1 = "leetcode", str2 = "codeleet"

› Output: false

💡 Note: Character 'e' would need to map to both 'e' and 't', which is impossible. We cannot have one character map to multiple different characters.

Example 3 — All Characters Used

$ Input: str1 = "abcdefghijklmnopqrstuvwxyz", str2 = "bcdefghijklmnopqrstuvwxyza"

› Output: false

💡 Note: This creates a cycle where 'a'→'b'→'c'→...→'z'→'a', but all 26 characters are used in str2, so we have no temporary character to break the cycle.

Constraints

1 ≤ str1.length ≤ 10⁴
str2.length == str1.length
str1 and str2 consist of lowercase English letters only

Visualization

Tap to expand

Understanding the Visualization

Input Strings

Two strings of equal length with character mapping requirements

Character Mapping

Build one-to-one mapping from source to target characters

Validation

Check consistency and cycle resolution possibility

Key Takeaway

🎯 Key Insight: Each character can only map to one target, and cycles need temporary characters for resolution

Asked in

G Google 35 f Facebook 28

The key insight is that each character in str1 must map to exactly one character in str2, and cycles can only be resolved if there's an unused character as temporary storage. Best approach is the Hash Map Validation method. Time: O(n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force Simulation	O(26^26)	O(n)	Try all possible conversion sequences until str1 matches str2
Hash Map Validation	O(n)	O(1)	Build character mapping and validate consistency rules

Brute Force Simulation — Algorithm Steps

Generate all possible character mappings
For each mapping, simulate the conversion
Check if result matches str2

Visualization

Tap to expand

Step-by-Step Walkthrough

Find Mismatch

Identify first character that differs between strings

Try Mapping

Attempt to map source character to target character

Recurse

Continue with updated string until match found or impossible

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

bool tryConversion(char* s1, char* s2, char mapping[26], bool usedChars[26]) {
    if (strcmp(s1, s2) == 0) return true;
    
    int len = strlen(s1);
    for (int i = 0; i < len; i++) {
        if (s1[i] != s2[i]) {
            char charFrom = s1[i];
            char charTo = s2[i];
            
            if (mapping[charFrom - 'a'] != 0) {
                if (mapping[charFrom - 'a'] != charTo) return false;
            } else {
                if (usedChars[charTo - 'a']) {
                    bool found = false;
                    for (int j = 0; j < 26; j++) {
                        if (mapping[j] == charTo) {
                            found = true;
                            break;
                        }
                    }
                    if (!found) {
                        for (char temp = 'a'; temp <= 'z'; temp++) {
                            if (!usedChars[temp - 'a']) {
                                char* newS1 = malloc(len + 1);
                                strcpy(newS1, s1);
                                for (int k = 0; k < len; k++) {
                                    if (newS1[k] == charFrom) newS1[k] = temp;
                                }
                                char newMapping[26];
                                bool newUsed[26];
                                memcpy(newMapping, mapping, sizeof(newMapping));
                                memcpy(newUsed, usedChars, sizeof(newUsed));
                                newUsed[temp - 'a'] = true;
                                bool result = tryConversion(newS1, s2, newMapping, newUsed);
                                free(newS1);
                                if (result) return true;
                            }
                        }
                    }
                }
                
                mapping[charFrom - 'a'] = charTo;
                usedChars[charTo - 'a'] = true;
                for (int j = 0; j < len; j++) {
                    if (s1[j] == charFrom) s1[j] = charTo;
                }
                return tryConversion(s1, s2, mapping, usedChars);
            }
        }
    }
    return false;
}

bool solution(char* str1, char* str2) {
    int len1 = strlen(str1);
    int len2 = strlen(str2);
    if (len1 != len2) return false;
    if (strcmp(str1, str2) == 0) return true;
    
    char mapping[26] = {0};
    bool usedChars[26] = {false};
    for (int i = 0; i < len2; i++) {
        usedChars[str2[i] - 'a'] = true;
    }
    
    char* s1_copy = malloc(len1 + 1);
    strcpy(s1_copy, str1);
    bool result = tryConversion(s1_copy, str2, mapping, usedChars);
    free(s1_copy);
    return result;
}

int main() {
    char str1[1001], str2[1001];
    fgets(str1, sizeof(str1), stdin);
    str1[strcspn(str1, "\n")] = 0;
    fgets(str2, sizeof(str2), stdin);
    str2[strcspn(str2, "\n")] = 0;
    
    bool result = solution(str1, str2);
    printf(result ? "true\n" : "false\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(26^26)

Up to 26 characters, each can map to any of 26 characters

✓ Linear Growth

Space Complexity

O(n)

Space for string copies during simulation

⚡ Linearithmic Space

24.5K Views

Medium Frequency

~35 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force Simulation — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler