Isomorphic Strings

19
3

Given strings s and t of same length, return true if consistently replacing the characters in s can produce t without changing their order. Different characters cannot share a replacement, but a character may map to itself. Otherwise, return false.

Example 1

Input: s = "noon", t = "peep"
Output: true
Explanation: Replacing n with p and o with e changes "noon" into "peep".

Example 2

Input: s = "ab", t = "cc"
Output: false
Explanation: Both a and b would need to map to c, which is not allowed.

Approach

Two strings are isomorphic if every character in s can be replaced by a fixed character to form t. The actual letters can differ, but their repetition pattern must match. For example, in "noon", the first and last letters are the same, and the two middle letters are the same, so any valid match like "peep" must repeat in the exact same places.

For this pattern to hold, each letter in s needs one fixed replacement in t, and that replacement cannot be claimed by any other letter from s. For instance, once 'n' is paired with 'p', 'n' must always become 'p', and no other letter like 'o' is allowed to also become 'p'. Tracking the relationship in both directions (from s to t and from t back to s) ensures both conditions: a letter in s can never change its replacement, and two different letters in s can never share the same replacement in t.

Algorithm

  • Compare the characters of s and t at corresponding positions from left to right.

  • If the current character from s was seen earlier and paired with a different replacement than the current character in t, the pattern is broken, so the strings are not isomorphic.

  • If the current character from t was already claimed earlier by a different character from s, two letters are trying to share one replacement, so the strings are not isomorphic.

  • If neither character has been paired yet, record the relationship in both directions so future positions can check against it.

  • Return true if every character pair from start to end follows these rules; return false immediately when a conflict occurs.

Dry Run

Isomorphic string

Isomorphic string

Solution

#include<bits/stdc++.h>
using namespace std;
class Solution {
public:
// Checks whether the strings have a consistent one-to-one mapping.
bool isomorphicString(const string& s, const string& t) {
if (s.length() != t.length()) {
return false;
}
// Store replacements in both directions.
unordered_map<char, char> forward;
unordered_map<char, char> reverse;
for (size_t i = 0; i < s.length(); i++) {
char source = s[i];
char target = t[i];
// A source character must keep its existing replacement.
if (forward.count(source) && forward[source] != target) {
return false;
}
// A target character cannot belong to two source characters.
if (reverse.count(target) && reverse[target] != source) {
return false;
}
// Record the matching pair after both checks pass.
forward[source] = target;
reverse[target] = source;
}
// Every character pair follows the same mapping rules.
return true;
}
};
// Driver code
int main() {
string s = "noon";
string t = "peep";
// Create an instance of class Solution.
Solution sol;
cout << boolalpha << sol.isomorphicString(s, t) << '\n';
return 0;
}

Complexity Analysis

Time Complexity: O(N), where N is the length of either string. Each corresponding character pair is checked once.

Space Complexity: O(1) auxiliary space. Since the strings contain only lowercase English letters, each mapping stores at most 26 entries.

Interview follow-up Questions

No. For example, "aabb" and "abab" have the same character counts, but they are not isomorphic: the first two occurrences of a would require different replacements. The positions of repeated characters must also match.

StringTCS NQT

Read Similar Blogs

Comments0