Isomorphic Strings Solution for Cognizant
Company: Cognizant · Difficulty: Medium · Topics: String, Hash Table
Problem Statement
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.
Examples
Example 1:
Input: s = "egg", t = "add"
Output: true
Explanation: 'e' → 'a', 'g' → 'd'
Example 2:
Input: s = "foo", t = "bar"
Output: false
Explanation: 'f' → 'b', 'o' → 'a', 'o' → 'r' (conflict)
Approach
Two Hash Maps Approach (Optimal)
1. Use two arrays to track character mappings
2. Map s[i] to t[i] and t[i] to s[i]
3. Check for conflicts in both directions
4. Return false if any conflict is found
Time and Space Complexity
- Time Complexity: O(n) where n is the length of the strings
- Space Complexity: O(1) since we use fixed-size arrays (ASCII characters)