Isomorphic Strings
Problem Description:
We are given two strings s, and t, and we need to figure out if they are isomorphic. Two strings s and t are isomorphic if we can replace characters in string s in such a way that it becomes string t.
Here are the key points to understand, for strings to be isomorphic:
- Each character in s should map to one and only one character in t.
- No two characters from s can map to the same character in t (though a character can map to itself).
Example 1:
Input: s = "bee" t = "att"
Output: true
Explanation:
'b' maps to 'a' and 'e' maps to 't', no two characters in s map to the same character in t.
Example 2:
Input: s = "aba" t = "xyz"
Output: false
Explanation:
‘a’ maps to ‘x’ and ‘z’, hence the strings are not isomorphic.
Constraints:
1 <= s.length <= 5 * 10⁴
t.length == s.length
s and t consist of any valid ascii character.
Brute Force Approach:
The first thing that comes to mind after reading the problem is to check each letter of string s and see how it maps to the letters in string t. For each letter in s, we would ensure that it matches with only one unique letter in t. If a letter from s maps to more than one letter in t, then we know the strings are not isomorphic, and we would return false. Otherwise, if every letter has a unique mapping, we can conclude that the strings are isomorphic.
How do we do this?
Since it's given in the problem that the lengths of both strings are equal, we start by going through each letter in s and attempt to map it to a corresponding letter in t. If a letter from s hasn’t been mapped yet, we assign it to the matching letter in t.
While performing this mapping, we make sure that no letter in s is mapped to more than one letter in t. Similarly, a letter in t should not be mapped to more than one letter from s.
If at any point we find that a letter in s maps to more than one letter in t, or vice versa, we return false immediately because this would break the isomorphic condition.
If we can check all characters without encountering any conflicts, we can confidently return true, meaning the strings are indeed isomorphic.
Let's walk through an example:
Let’s dry run the example s = "data" and t = "meta" using the approach.
1. i = 0:
s[0] = 'd' and t[0] = 'm'.
Now, check if ‘d’ comes again in string s, after index i.
The inner loop starts (j iterating from i + 1).
j = 1:
Compare s[0] with s[1] ('d' with 'a'): No match, continue.
Compare t[0] with t[1] ('m' with 'e'): No match, continue.
j = 2:
Compare s[0] with s[2] ('d' with 't'): No match, continue.
Compare t[0] with t[2] ('m' with 't'): No match, continue.
j = 3:
Compare s[0] with s[3] ('d' with 'a'): No match, continue.
Compare t[0] with t[3] ('m' with 'a'): No match, continue.
2. i = 1:
s[1] = 'a' and t[1] = 'e'.
Now, check if ‘a’ comes again in string s, after the index i.
The inner loop starts.
j = 2:
Compare s[1] with s[2] ('a' with 't'): No match, continue.
Compare t[1] with t[2] ('e' with 't'): No match, continue.
j = 3:
Compare s[1] with s[3] ('a' with 'a'): Match found.
Compare t[1] with t[3] ('e' with 'a'): A mismatch is found, as ‘e’ is matched with ‘a’ previously.Return false immediately.
Conclusion:
The brute force approach determines that the strings "data" and "meta" are not isomorphic because the character 'a' from s maps to both 'e' and 'a' in t, violating the isomorphic condition. Thus, the function would return false.
Now, How to Code It Up?
We take a loop to traverse the string s and map each character to the corresponding character in t.
Then, for each character in s[i], we take another loop to check the rest of the string s[i+1...n].
For each matching character s[i] == s[j], we ensure that t[i] == t[j]. If it doesn’t, the strings aren’t isomorphic.
If no conflicts are found, return true.
Code Implementation
1. C++ Try on Compiler
class Solution {
public:
bool isIsomorphic(string s, string t) {
// Traverse each character of the string s
for (int i = 0; i < s.length(); i++) {
// Map the current character of s to its corresponding character in
// t
char sChar = s[i];
char tChar = t[i];
// Now, take another loop to check if any other occurrence of sChar
// exists
for (int j = i + 1; j < s.length(); j++) {
// If sChar occurs again in s[j], its corresponding character in
// t should also match
if (s[i] == s[j] && t[i] != t[j]) {
// Mismatch found, not isomorphic
return false;
}
// If s[i] and s[j] are different, their corresponding t[i] and
// t[j] must also be different
if (s[i] != s[j] && t[i] == t[j]) {
// Mismatch found, not isomorphic
return false;
}
}
}
return true;
}
};2. Java Try on Compiler
class Solution {
public boolean isIsomorphic(String s, String t) {
// Traverse each character of the string s
for (int i = 0; i < s.length(); i++) {
// Map the current character of s to its corresponding character in t
char sChar = s.charAt(i);
char tChar = t.charAt(i);
// Now, take another loop to check if any other occurrence of sChar exists
for (int j = i + 1; j < s.length(); j++) {
// If sChar occurs again in s[j], its corresponding character in t should also match
if (s.charAt(i) == s.charAt(j) && t.charAt(i) != t.charAt(j)) {
// Mismatch found, not isomorphic
return false;
}
// If s[i] and s[j] are different, their corresponding t[i] and t[j] must also be different
if (s.charAt(i) != s.charAt(j) && t.charAt(i) == t.charAt(j)) {
// Mismatch found, not isomorphic
return false;
}
}
}
return true;
}
}3. Python Try on Compiler
class Solution(object):
def isIsomorphic(self, s, t):
# Traverse each character of the string s
for i in range(len(s)):
# Map the current character of s to its corresponding character in t
sChar = s[i]
tChar = t[i]
# Now, take another loop to check if any other occurrence of sChar exists
for j in range(i + 1, len(s)):
# If sChar occurs again in s[j], its corresponding character in t should also match
if s[i] == s[j] and t[i] != t[j]:
# Mismatch found, not isomorphic
return False
# If s[i] and s[j] are different, their corresponding t[i] and t[j] must also be different
if s[i] != s[j] and t[i] == t[j]:
# Mismatch found, not isomorphic
return False
return True
4. Javascript Try on Compiler
var isIsomorphic = function(s, t) {
// Traverse each character of the string s
for (let i = 0; i < s.length; i++) {
// Map the current character of s to its corresponding character in t
let sChar = s[i];
let tChar = t[i];
// Now, take another loop to check if any other occurrence of sChar exists
for (let j = i + 1; j < s.length; j++) {
// If sChar occurs again in s[j], its corresponding character in t should also match
if (s[i] === s[j] && t[i] !== t[j]) {
// Mismatch found, not isomorphic
return false;
}
// If s[i] and s[j] are different, their corresponding t[i] and t[j] must also be different
if (s[i] !== s[j] && t[i] === t[j]) {
// Mismatch found, not isomorphic
return false;
}
}
}
return true;
};Time Complexity: O(n²)
In our solution, we utilize two nested loops to check if the strings are isomorphic.
Outer Loop (indexed by i): Runs from 0 to n-1.So, it iterates n times.
Inner Loop (indexed by j): For each fixed i, j runs from i+1 to n-1.When i = 0, j runs n-1 times.When i = 1, j runs n-2 times.When i = 2, j runs n-3 times.…When i = n-1, j runs 0 time.
Total Iterations: To find the total number of iterations of the inner loop across all iterations of the outer loop, we sum up the iterations for each value of i:
∑ (n-i-1) i=0 to n−1This is the sum of an arithmetic series: (n−1)+(n−2)+…+1 + 0.
If we closely observe and reverse the series we get 1 + 2 + 3 + … + (n-2) + (n-1) .
That is nothing but the sum of n-1 terms.So the sum of n numbers from 1 to n is (n*(n+1))/2.
Thus, the total number of operations from 1 to n-1 will be (n*(n-1))/2.
In Big-O notation, we focus on the term that grows the fastest as n increases, and we ignore constant factors and lower-order terms. Therefore: O((n*(n-1))/2) ≈ O(n²)
Space Complexity: O(n)
In our algorithm, we primarily utilize a few variables to temporarily store the characters being processed, specifically sChar and tChar. Therefore, the space complexity is constant, i.e., O(1).
Auxiliary Space: O(1)
Explanation: The auxiliary space used by the algorithm is O(1) since we're only using a fixed number of variables (sChar and tChar), regardless of the input size.
Total Space Complexity: O(n)
Explanation: So, the overall space complexity is dominated by the input strings, making it O(n).
Will Brute Force Work Against the Given Constraints?
Let's evaluate whether the brute force method is suitable for the constraints outlined in the problem. The problem states that the size of the input strings, n, can reach up to 50,000. In our brute force approach, we employ nested loops to compare characters, resulting in n * n comparisons for each character in the string.
If we consider the maximum constraint of n=50,000, this would lead to approximately 2.5 billion operations (i.e., 2.5*10⁹). This number far exceeds the typical limits of competitive programming environments, which can generally handle around 10⁷ to 10⁸ operations within a reasonable time frame.
While the brute force approach might have been feasible for smaller input sizes, such as n ≤ 1,000 where the total operations would be around 1 million (10⁶), this is manageable within standard time constraints for most programming challenges.
However, with larger values of n, the brute force method becomes impractical.
So, while the brute force approach will technically work and give the right answer, it’s far from efficient when dealing with larger input sizes and can’t handle the upper limits of the constraints.
Can we optimize it?
Now we understand, to determine if two strings are isomorphic, we must establish a precise mapping between the characters of the first string and those of the second string. Each letter in the first string should correspond to exactly one letter in the second string, ensuring that this relationship remains consistent throughout the strings.
The brute force approach involves using nested loops to compare every character in the first string with every character in the second string. While this method is straightforward, it results in O(n²) time complexity due to the repeated comparisons.
But what if we eliminate the need for a second loop?
What if we think of the character mapping like a one-to-one function?
In mathematics, a one-to-one (or injective) function is a function where each input has a unique output, and no two inputs can map to the same output. This is exactly what we want when mapping characters from one string to another. Each character in the first string(input) should map to one distinct character in the second string(output), with no overlap.
By thinking of character mapping in terms of this one-to-one function, we can simplify the process. Instead of checking each character against all others in nested loops, we can create a mapping as we go.
As we traverse the characters, we can create a mapping for each character in the first string to its corresponding character in the second string.
For instance, if we encounter 'a' in the first string, we check its current mapping and ensure it hasn’t been previously assigned to a different character. If a conflict arises, we can immediately return false, confirming that the strings are not isomorphic.
This approach maintains a time complexity of O(n) and avoids redundant comparisons, making it much more efficient and suitable for larger input sizes.
Let’s see an example to be clear!
Let’s consider the strings s = "paper" and t = "title."
Iteration Over the Strings:
- i = 0:
s[i] == 'p' and t[i] == 't'
Map 'p' to 't': p -> t
- i = 1:
s[i] == 'a' and t[i] == 'i'
Map 'a' to 'i': a -> i
- i = 2:
s[i] == 'p' and t[i] == 't''
p' is already mapped to 't', so no action needed: p -> t
- i = 3:
s[i] == 'e' and t[i] == 'l'
Map 'e' to 'l': e -> l
- i = 4:
s[i] == 'r' and t[i] == 'e'
Map 'r' to 'e': r -> e
Final Mapping Summary:
- Mappings established:
- p -> t
- a -> i
- e -> l
- r -> e
Conclusion:
All characters are consistently mapped without conflicts, so the strings "paper" and "title" are isomorphic.
Let's understand with visuals
Consider one more example:
Let’s consider the strings s = "label" and t = "cable."
Iteration Over the Strings:
- i = 0:
s[i] == 'l' and t[i] == 'c'
Map 'l' to 'c': l -> c
- i = 1:
s[i] == 'a' and t[i] == 'a'
Map 'a' to 'a': a -> a
- i = 2:
s[i] == 'b' and t[i] == 'b'
Map 'b' to 'b': b -> b
- i = 3:
s[i] == 'e' and t[i] == 'l'
Map 'e' to 'l': e -> l
- i = 4:
s[i] == 'l' and t[i] == 'e'
'l' is already mapped to 'c', but here it would need to map to 'e' which causes a conflict.
Final Mapping Summary:
- Mappings established:
- l -> c
- a -> a
- b -> b
- e -> l
Conclusion:
Since there is a conflict with the mapping of 'l', the strings "label" and "cable" are not isomorphic.
How to convert it into code?
So, it's clear we need to map the letters of a string to another. So, which data structure can we use here?
Yes, exactly! We can use a hash table.
Why hash table?
The beauty of using a hash table lies in its constant-time complexity for both insertions and lookups, which makes our solution efficient. This dynamic mapping not only simplifies the implementation but also allows us to handle various characters easily. Thus, a hash table is the perfect choice for solving this problem!
A hash table allows us to create efficient mappings between characters. As we iterate through the strings, we can check if a character from the first string has already been mapped to a character in the second string.
If it hasn't been mapped yet, we can add it to our hash table. If we find that it is already mapped to a different character, we know the strings can't be isomorphic.
We'll set up two hash tables (or auxiliary arrays) to store the mappings of characters from the first string to the second string and vice versa.
Note - We’ll take a hash table of size 256 as input strings can contain any valid ascii character, which ranges from 0 to 255.
This way, we can keep track of which characters correspond to each other.
Now, we can loop through each character in both strings simultaneously. For each pair of characters:
- We check if the character from the first string is already mapped to a character in the second string. If it is, we verify that it matches the current character in the second string.
- If there’s no existing mapping, we create one. We'll also check the reverse mapping to ensure that the character in the second string isn’t already mapped to a different character from the first string.
If at any point we find a mismatch—where a character from the first string maps to two different characters in the second string or vice versa—we can conclude that the strings are not isomorphic and return false.
If we successfully process all characters without finding any conflicts, we can safely conclude that the two strings are isomorphic and return true.
In this way, we can efficiently check if two strings are isomorphic or not.
Code Implementation
1. C++ Try on Compiler
class Solution {
public:
bool isIsomorphic(string s, string t) {
if (s.length() != t.length()) return false;
// Arrays to store mappings of characters from s to t and t to s
vector<int> mapST(256, -1); // Mapping s -> t
vector<int> mapTS(256, -1); // Mapping t -> s
for (int i = 0; i < s.length(); i++) {
char sChar = s[i];
char tChar = t[i];
// Check if sChar already maps to tChar
if (mapST[sChar] == -1) {
// Create mapping s -> t
mapST[sChar] = tChar;
} else if (mapST[sChar] != tChar) {
// Mismatch in mapping
return false;
}
// Check if tChar already maps to sChar
if (mapTS[tChar] == -1) {
// Create mapping t -> s
mapTS[tChar] = sChar;
} else if (mapTS[tChar] != sChar) {
// Mismatch in reverse mapping
return false;
}
}
return true;
}
};2. Java Try on Compiler
class Solution {
public boolean isIsomorphic(String s, String t) {
if (s.length() != t.length()) return false;
// Arrays to store mappings of characters from s to t and t to s
int[] mapST = new int[256]; // Mapping s -> t
int[] mapTS = new int[256]; // Mapping t -> s
// Initialize arrays to -1
Arrays.fill(mapST, -1);
Arrays.fill(mapTS, -1);
for (int i = 0; i < s.length(); i++) {
char sChar = s.charAt(i);
char tChar = t.charAt(i);
// Check if sChar already maps to tChar
if (mapST[sChar] == -1) {
// Create mapping s -> t
mapST[sChar] = tChar;
} else if (mapST[sChar] != tChar) {
// Mismatch in mapping
return false;
}
// Check if tChar already maps to sChar
if (mapTS[tChar] == -1) {
// Create mapping t -> s
mapTS[tChar] = sChar;
} else if (mapTS[tChar] != sChar) {
// Mismatch in reverse mapping
return false;
}
}
return true;
}
}3. Python Try on Compiler
class Solution(object):
def isIsomorphic(self, s, t):
if len(s) != len(t):
return False
# Arrays to store mappings of characters from s to t and t to s
mapST = [-1] * 256 # Mapping s -> t
mapTS = [-1] * 256 # Mapping t -> s
for i in range(len(s)):
sChar = ord(s[i])
tChar = ord(t[i])
# Check if sChar already maps to tChar
if mapST[sChar] == -1:
# Create mapping s -> t
mapST[sChar] = tChar
elif mapST[sChar] != tChar:
# Mismatch in mapping
return False
# Check if tChar already maps to sChar
if mapTS[tChar] == -1:
# Create mapping t -> s
mapTS[tChar] = sChar
elif mapTS[tChar] != sChar:
# Mismatch in reverse mapping
return False
return True
4. Javascript Try on Compiler
var isIsomorphic = function(s, t) {
if (s.length !== t.length) return false;
// Arrays to store mappings of characters from s to t and t to s
let mapST = new Array(256).fill(-1); // Mapping s -> t
let mapTS = new Array(256).fill(-1); // Mapping t -> s
for (let i = 0; i < s.length; i++) {
let sChar = s.charCodeAt(i);
let tChar = t.charCodeAt(i);
// Check if sChar already maps to tChar
if (mapST[sChar] === -1) {
// Create mapping s -> t
mapST[sChar] = tChar;
} else if (mapST[sChar] !== tChar) {
// Mismatch in mapping
return false;
}
// Check if tChar already maps to sChar
if (mapTS[tChar] === -1) {
// Create mapping t -> s
mapTS[tChar] = sChar;
} else if (mapTS[tChar] !== sChar) {
// Mismatch in reverse mapping
return false;
}
}
return true;
};Time Complexity: O(n)
We traverse both strings once from index i = 0 to n, where n is the length of the strings. Since all operations involving the hash tables are executed in constant time, the overall time complexity is O(n).
Space Complexity: O(n)
While the algorithm itself uses only two hash tables of size 256, apart from the input strings, the total space complexity of the solution is O(n).
Auxiliary Space: O(1)
Explanation: The auxiliary space used by the algorithm is O(1) since we're only using two hash tables of size 256, which is a constant.
Total Space Complexity: O(n)
Explanation: So, the overall space complexity is dominated by the input strings, making it O(n).
Learning Tip
Now we have successfully tackled this problem, let's try these similar problems.
Given an array nums of size n, return the majority element.
The majority element is the element that appears more than ⌊n / 2⌋ times. You may assume that the majority element always exists in the array.
Given an integer array nums, return the most frequent even element.
If there is a tie, return the smallest one. If there is no such element, return -1.