Isomorphic Strings Java Solution with HashMap

The isomorphic strings problem requires determining if two strings can be mapped to each other through a bijective character mapping. This solution uses HashMap to track character correspondences while handling edge cases like different string lengths and inconsistent mappings.

1. Problem Restatement

Clarifying questions to ask the interviewer:

1. Can the input strings be of different lengths? If so, should we return false immediately?
2. Are the strings guaranteed to be non-null and non-empty?
3. Do we need to handle Unicode characters or only ASCII?
4. Should the mapping be bijective (both directions must be consistent)?
5. What is the expected time complexity for the solution? Should we aim for O(n) or can we accept O(n²)?

Restated problem:
Given two strings s and t, determine whether they are isomorphic. Two strings are isomorphic if the characters in s can be mapped to characters in t such that:

• Each character in s maps to exactly one character in t
• Each character in t maps to exactly one character in s (bijective mapping)
• The relative order of characters is preserved

Input/output specification:

• Input: Two strings s and t of equal length
• Output: Boolean value indicating whether the strings are isomorphic

Constraints:

• Both strings have equal length (assumption from problem context)
• Strings can be of any reasonable size (up to 5 * 10^4 characters)
• Characters can be any valid ASCII or Unicode characters

Assumptions:

• Both strings will have the same length (this is implied by the problem definition)
• We are looking for a bijective character mapping between the strings
• The solution should handle all valid character inputs including special characters and spaces

Data shape and hidden structure: The problem involves a one-to-one mapping relationship between characters in two strings. The key insight is that we need to maintain a consistent mapping in both directions, which suggests using hash maps to track character correspondences. The structure is essentially a graph matching problem where we're checking if two strings form isomorphic graphs with directed edges representing character mappings.

2. Pattern Recognition

Identifying the pattern

The key pattern here is character mapping bijection - we need to establish a one-to-one correspondence between characters in two strings.

Wording that signals the pattern

• "isomorphic" - this directly indicates we're looking for structural similarity in character mappings
• The requirement that "same position characters must map to same characters" signals a bi-directional mapping constraint
• The need to preserve relative order and character relationships points to pattern matching through mapping

Why this fits the pattern

This problem requires us to verify that two strings maintain consistent character-to-character relationships. It's fundamentally about checking if there exists a bijective mapping between characters of the two strings, which is a classic pattern for string isomorphism problems.

Core insight

The critical insight is that we need to maintain a bidirectional character mapping - for every character in string1, there must be exactly one corresponding character in string2, and vice versa. This means we need to track two mappings simultaneously: s1 -> s2 and s2 -> s1.

This pattern appears in many string matching problems where we need to verify structural consistency between two sequences, particularly when dealing with character substitution ciphers or pattern matching problems.

3. Approach Evolution

My first instinct is to check if two strings are isomorphic by mapping characters from one string to another. A brute force approach would be to check every character position and verify that the mapping is consistent, but that's O(n²) because for each character we might need to scan the entire string to verify the mapping pattern.

Let me think about how to optimize this. I notice that if I maintain a consistent character mapping relationship, I can reduce it to O(n) by using two hash maps to track the forward and reverse mappings. This way, I can process each character once and verify that no conflicting mappings exist.

The key insight is that for strings to be isomorphic, there must be a bijective mapping between characters in string s and string t. This means each character in s maps to exactly one character in t, and vice versa.

My approach will be:

1. Use two hash maps to maintain forward and reverse character mappings
2. Process each character position from left to right
3. For each pair of characters, check if there's a consistent mapping
4. If any conflict is found, return false immediately

This approach ensures O(n) time complexity where n is the length of the strings, and O(k) space where k is the size of the character set.

Let me trace through this more carefully - I need to ensure that both mappings are consistent at each step. If character s[i] maps to t[j] but s[i] was previously mapped to a different character, or if t[j] is already mapped to a different character from s[i], then the strings aren't isomorphic.

The invariant I must maintain is that at any point during processing, if s[i] has been mapped to t[j], then:

1. No other character in s should map to t[j]
2. No other character in t should map to s[i]

This ensures the bijective relationship is preserved throughout the algorithm.

4. Data Structure Choice

For this isomorphic strings problem, I need to track character mappings between the two strings to ensure they maintain a consistent one-to-one relationship.

The primary data structure I'll use is a HashMap<Character, Character> to store the character mappings from string s to string t. This allows me to efficiently check if a character in s has already been mapped to a specific character in t, and to verify consistency when new mappings are attempted.

I also need to handle the bidirectional nature of isomorphism - if s[i] maps to t[j], then t[j] should not already be mapped to a different character from s. To handle this efficiently, I'll use a second HashMap<Character, Character> to track the reverse mapping from t to s.

Why these data structures:

• HashMap provides O(1) average lookup and insertion time, which is crucial for maintaining O(n) linear time complexity
• The bidirectional mapping ensures I can detect when a character in t is already mapped to a different character in s, preventing invalid one-to-one mappings
• Using two hash maps instead of trying to encode both directions in one structure keeps the logic clean and readable

Space impact: O(k) where k is the number of unique characters in the strings, which is at most 26 for lowercase English letters but scales with the character set size.

Helper structure: No additional helper structures needed beyond the two HashMaps that serve as the core mapping mechanisms.

The choice of HashMap over other structures like arrays (for ASCII characters) or custom classes is driven by the need for flexibility - it works with any character set and handles the bidirectional mapping naturally without requiring complex encoding schemes.

5. Algorithm Walkthrough

Let me trace through the algorithm with a concrete example to show how it works step-by-step.

Example: s = "egg", t = "add"

Step 1: Initialize empty mapping hashmaps

• charMapSToT = {}
• charMapTToS = {}

Step 2: Process first character pair (e, a)

• charMapSToT is empty, so map 'e' → 'a'
• charMapTToS is empty, so map 'a' → 'e'
• Both mappings created successfully

Step 3: Process second character pair (g, d)

• charMapSToT has 'e' → 'a', so we check if 'g' maps to 'd'
• 'g' is not in the map, so create mapping 'g' → 'd'
• charMapTToS has 'a' → 'e', so we check if 'd' maps to 'g'
• 'd' is not in the map, so create mapping 'd' → 'g'

Step 4: Process third character pair (g, d)

• charMapSToT has 'e' → 'a', 'g' → 'd'
• Check if 'g' maps to 'd' - it does ✓
• charMapTToS has 'a' → 'e', 'd' → 'g'
• Check if 'd' maps to 'g' - it does ✓
• Both mappings consistent, continue

Step 5: Return true since all character pairs are consistently mapped

Edge case handling: If we had s = "foo", t = "bar":

• First pair (f, b) → map 'f' → 'b', 'b' → 'f'
• Second pair (o, a) → map 'o' → 'a', 'a' → 'o'
• Third pair (o, r) → 'o' already maps to 'a', but we're trying to map it to 'r'
• This inconsistency causes early return false

The algorithm maintains bidirectional mapping invariants throughout the process, ensuring that character relationships are preserved in both directions.

6. Java Solution

public class IsomorphicStrings {
    public boolean areIsomorphic(String s, String t) {
        // Handle edge cases
        if (s == null || t == null) {
            return false;
        }
        
        if (s.length() != t.length()) {
            return false;
        }
        
        // Maps to store character mappings from s -> t and t -> s
        Map<Character, Character> mapSToT = new HashMap<>();
        Map<Character, Character> mapTToS = new HashMap<>();
        
        // Iterate through each character pair
        for (int i = 0; i < s.length(); i++) {
            char charS = s.charAt(i);
            char charT = t.charAt(i);
            
            // Check if we have a conflicting mapping in s -> t
            if (mapSToT.containsKey(charS)) {
                if (mapSToT.get(charS) != charT) {
                    return false;
                }
            } else {
                // Create new mapping from s to t
                mapSToT.put(charS, charT);
            }
            
            // Check if we have a conflicting mapping in t -> s
            if (mapTToS.containsKey(charT)) {
                if (mapTToS.get(charT) != charS) {
                    return false;
                }
            } else {
                // Create new mapping from t to s
                mapTToS.put(charT, charS);
            }
        }
        
        return true;
    }
}

This solution uses two hash maps to maintain bidirectional character mappings between the strings. For each character position, we check if there's already a mapping and whether it's consistent with the current character pair. The bidirectional check ensures that both strings maintain a one-to-one mapping relationship, which is the definition of isomorphic strings.

7. Complexity Analysis

Time Complexity: O(n) where n is the length of the strings. We iterate through each string exactly once, performing constant-time operations (hash map lookups and updates) at each step.

Space Complexity: O(k) where k is the size of the character set (at most 256 for ASCII characters). In the worst case, we store all unique characters from both strings in our hash maps. For Unicode characters, this could be up to O(n) if all characters are unique.

Why these bounds are correct:

• The linear iteration ensures O(n) time complexity
• Hash map operations (put/get) are O(1) amortized
• The space usage is bounded by the unique characters in the input, which cannot exceed the character set size
• These bounds are optimal because we must examine each character at least once to determine isomorphism

Optimality: This solution achieves optimal time and space complexity for the problem. Any correct algorithm must examine each character at least once, making O(n) time unavoidable. The space complexity is also optimal since we need to store mappings for potentially all unique characters.

The solution is near-optimal because it avoids any unnecessary operations or redundant data structures that would increase complexity beyond the theoretical minimum.

8. Edge Cases & Pitfalls

Empty and minimal inputs

• Empty strings should return true (both empty, so isomorphic)
• Single character strings should return true (only one mapping needed)
• One empty string and one non-empty string should return false

Duplicate values and repeated states

• When mapping from s to t, if we encounter a character in t that was already mapped to by a different character in s, we have a conflict
• When mapping from t to s, we must ensure the reverse mapping is also consistent
• Example: s = "ab", t = "aa" - first char maps correctly, but second char tries to map 'a' to both 'b' and 'a'

Boundary conditions

• Strings of different lengths should return false immediately (no need for mapping)
• Very long strings (approaching Integer.MAX_VALUE) - though Java string length is limited to 2^31-1, so this isn't a practical concern

Common implementation mistakes

• Unidirectional mapping only: Only checking mapping from s to t but not the reverse can lead to false positives
• Incorrect mapping validation: Not properly checking that each character maps consistently to the same target character
• Null pointer exceptions: Failing to handle null inputs gracefully (though problem statement implies valid strings)
• Character range assumptions: Assuming ASCII characters only without considering Unicode or extended character sets
• HashMap key collision handling: While unlikely with char keys, improper handling of hash collisions could cause issues

The most critical pitfall is failing to maintain bidirectional consistency - a robust solution must verify that both string-to-string and string-to-string reverse mappings are consistent throughout the traversal.

9. Alternative Approaches

There are several alternative approaches to solving the isomorphic strings problem, each with different trade-offs:

Approach 1: Two HashMaps Instead of using a single HashMap with a custom class, we can maintain two separate HashMaps - one mapping characters from string s to string t, and another mapping characters from string t to string s. This approach ensures bidirectional uniqueness checks but requires more memory and slightly more complex logic.

Approach 2: Character Position Mapping We can map each character to the positions where it appears in the string. For example, if "egg" has 'e' at position 0 and 'g' at positions 1, 2, we can create a pattern representation. Two strings are isomorphic if they have identical pattern representations. This approach requires O(n) time for pattern generation but can be more intuitive for some developers.

Approach 3: Canonical Form Mapping Convert both strings to canonical forms by mapping each unique character to a sequence of integers (e.g., first unique char → 0, second unique char → 1, etc.). If both strings convert to the same canonical form, they are isomorphic. This approach has similar complexity but might be more readable.

Trade-offs Analysis: The original solution using a single HashMap with custom class is optimal in both time and space complexity. The two-HashMap approach adds constant factor overhead in memory usage and code complexity. The canonical form approach requires additional processing to generate the canonical representation, making it less efficient for this specific problem.

The chosen solution is preferred because it's the most direct implementation of the core mapping requirement, with optimal O(n) time and O(k) space complexity where k is the size of the character set, making it both time and space efficient for the problem constraints.

10. Test Cases

public class IsomorphicStrings {
    public boolean areIsomorphic(String s, String t) {
        if (s.length() != t.length()) return false;
        
        Map<Character, Character> sToT = new HashMap<>();
        Map<Character, Character> tToS = new HashMap<>();
        
        for (int i = 0; i < s.length(); i++) {
            char sChar = s.charAt(i);
            char tChar = t.charAt(i);
            
            if (sToT.containsKey(sChar)) {
                if (sToT.get(sChar) != tChar) return false;
            } else {
                sToT.put(sChar, tChar);
            }
            
            if (tToS.containsKey(tChar)) {
                if (tToS.get(tChar) != sChar) return false;
            } else {
                tToS.put(tChar, sChar);
            }
        }
        
        return true;
    }
}

The test cases below validate the solution's correctness across various scenarios:

Sample Test Cases

// Test case 1: Basic isomorphic strings
assertEquals(true, areIsomorphic("egg", "add"));

// Test case 2: Non-isomorphic strings (mapping conflict)
assertEquals(false, areIsomorphic("foo", "bar"));

// Test case 3: Different lengths
assertEquals(false, areIsomorphic("ab", "aa"));

// Test case 4: Empty strings
assertEquals(true, areIsomorphic("", ""));

// Test case 5: Single character strings
assertEquals(true, areIsomorphic("a", "b"));

// Test case 6: Complex isomorphic mapping
assertEquals(true, areIsomorphic("paper", "title"));

// Test case 7: Duplicate characters in both strings
assertEquals(false, areIsomorphic("ab", "aa"));

// Test case 8: Same characters in different positions
assertEquals(false, areIsomorphic("abc", "def"));

Tricky Test Case

// Test case 9: Complex mapping with multiple character reuse
// "abba" maps to "abab" - this should return false because:
// a -> a, b -> b, b -> a (conflict), a -> b (conflict)
assertEquals(false, areIsomorphic("abba", "abab"));

Boundary Test Case

// Test case 10: Large strings with valid isomorphic mapping
String s = "abcdefghijklmnopqrstuvwxyz".repeat(1000);
String t = "zyxwvutsrqponmlkjihgfedcba".repeat(1000);
assertEquals(true, areIsomorphic(s, t));

These test cases cover:

• Basic isomorphic string validation
• Mapping conflicts that break isomorphism
• Length mismatches
• Empty and single character edge cases
• Complex mapping patterns with multiple character reuse
• Boundary conditions with large inputs

11. Final Summary

The core insight is that two strings are isomorphic if and only if there exists a bijective mapping between characters of the first string to characters of the second string. This means each character in the first string maps to exactly one character in the second string, and vice versa.

The solution works by maintaining two hash maps to track the character mappings in both directions, ensuring no conflicting mappings occur. This approach is optimal with O(n) time and space complexity where n is the length of the strings, as we must examine each character at least once to validate the isomorphic relationship.

What makes this solution efficient is that it handles both directions of the mapping simultaneously, preventing false positives from one-way mapping checks. The use of hash maps provides O(1) average lookup and insertion times, making the overall solution linear in both time and space complexity.