Isomorphic Strings - Practice Coding Problems

Isomorphic Strings - Problem

Given two strings s and t, determine if they are isomorphic.

Two strings s and t are isomorphic if the characters in s can be replaced to get t.

All occurrences of a character must be replaced with another character while preserving the order of characters. No two characters may map to the same character, but a character may map to itself.

Input & Output

Example 1 — Basic Isomorphic Case

$ Input: s = "egg", t = "add"

› Output: true

💡 Note: Characters map consistently: 'e'→'a', 'g'→'d'. Pattern is preserved: first char different from next two, which are identical.

Example 2 — Non-Isomorphic Case

$ Input: s = "foo", t = "bar"

› Output: false

💡 Note: Character 'o' appears twice in s but maps to different characters in t: 'o'→'a' and 'o'→'r'. This violates isomorphic property.

Example 3 — Identity Mapping

$ Input: s = "paper", t = "title"

› Output: true

💡 Note: Valid mappings: 'p'→'t', 'a'→'i', 'p'→'t', 'e'→'l', 'r'→'e'. Each character maps consistently to exactly one other character.

Constraints

1 ≤ s.length ≤ 5 × 10⁴
t.length == s.length
s and t consist of any valid ASCII character

Visualization

Tap to expand

Understanding the Visualization

Input Strings

Two strings s and t of equal length

Character Mapping

Check if characters can be mapped consistently

Validation Result

Return true if mapping is bijective and consistent

Key Takeaway

🎯 Key Insight: Two strings are isomorphic if they have identical character occurrence patterns and maintain consistent one-to-one mapping

Asked in

G Google 15 a Amazon 12 M Microsoft 8 f Facebook 6

The key insight is that isomorphic strings must have identical character patterns. Best approach uses bidirectional hash maps to ensure one-to-one character mapping in a single pass. Time: O(n), Space: O(k) where k is the number of unique characters.

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force Pattern Matching	O(n²)	O(1)	Check all character positions and verify mapping consistency
Single Pass with Array Mapping	O(n)	O(1)	Use character arrays for O(1) lookup instead of hash maps
Hash Map Bidirectional Mapping	O(n)	O(k)	Use two hash maps to track character mappings in both directions

Brute Force Pattern Matching — Algorithm Steps

Compare character patterns at each position
Build mapping from s to t
Verify no conflicts in reverse mapping

Visualization

Tap to expand

Step-by-Step Walkthrough

Compare Positions

Check if same characters map consistently

Verify Mapping

Ensure no conflicts in character mapping

Result

Return true if all patterns match

Code -

solution.c — C

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

bool solution(char* s, char* t) {
    int len_s = strlen(s);
    int len_t = strlen(t);
    if (len_s != len_t) return false;
    
    for (int i = 0; i < len_s; i++) {
        for (int j = i + 1; j < len_s; j++) {
            if (s[i] == s[j] && t[i] != t[j]) return false;
            if (s[i] != s[j] && t[i] == t[j]) return false;
        }
    }
    return true;
}

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

Time & Space Complexity

Time Complexity

⏱️

O(n²)

For each character, we may scan the entire string to find all occurrences

⚠ Quadratic Growth

Space Complexity

O(1)

Only using constant extra space for comparisons

✓ Linear Space

102.5K Views

Medium Frequency

~15 min Avg. Time

2.8K 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 Pattern Matching — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler