Isomorphic Strings in Java: Algorithm, Code and Examples

Two strings are isomorphic when we can replace every character of the first string with another character to get the second string, and the mapping is one-to-one, so no two characters map to the same character. For example, “abbcdd” and “qwwcrr” are isomorphic, because a always becomes q, b becomes w, c stays c and d becomes r.

We check for isomorphic strings when two texts must follow the same letter pattern, such as in word pattern puzzles and substitution ciphers. The check is also a common coding interview question, known as LeetCode problem 205.

The following example checks a few pairs with a Java method isIsomorphic() that stores the mapping in two HashMap objects, one for each direction. We build the method in section 4.2.

boolean same = isIsomorphic("abbcdd", "qwwcrr");     // true
boolean twoTargets = isIsomorphic("aab", "que");     // false (a -> q and a -> u)
boolean twoSources = isIsomorphic("abc", "xxy");     // false (a -> x and b -> x)
boolean selfMap = isIsomorphic("noon", "noon");      // true (a character may map to itself)
boolean lengths = isIsomorphic("ab", "abc");         // false (different lengths)
boolean nulls = isIsomorphic(null, "abc");           // false

Notice the third pair. Every character of “abc” has one partner, but a and b both map to x, so the strings are not isomorphic. A correct check looks at both directions.

Next, we write the algorithm and two Java versions of it, one with arrays and one with maps, and compare their speed and memory use.

1. What are Isomorphic Strings?

Two strings are isomorphic if we can map every character of the first string to a character of the second string in a one-to-one fashion. The order of the characters stays the same, and every occurrence of a character gets the same replacement. A character may also map to itself.

For example, consider that the first string is “abbcdd” and the second string is “qwwcrr“. We put the two strings on top of each other and read the pairs at each index.

As we can see, the character ‘a‘ of the first string is replaced by the character ‘q‘ of the second string. The character ‘b‘ is replaced by ‘w‘, ‘c‘ stays ‘c‘ and ‘d‘ is replaced by ‘r‘. The vice-versa is also true, so we can turn “qwwcrr” back into “abbcdd“. In other words, these two strings are isomorphic.

Let us take another example of strings “aab” and “que“. These two strings are not isomorphic because ‘a‘ cannot be mapped to both ‘q‘ and ‘u‘.

The mapping must hold in both directions. The pair “abc” and “xxy” passes a one-way check, because a, b and c each get one partner. But x gets two partners, a and b, so we cannot turn “xxy” back into “abc”.

String 1	String 2	Isomorphic?	Reason
“abbcdd”	“qwwcrr”	yes	a-q, b-w, c-c, d-r
“noon”	“noon”	yes	every character maps to itself
“deer”	“book”	yes	d-b, e-o, r-k
“aab”	“que”	no	a maps to q and to u
“abc”	“xxy”	no	a and b both map to x
“ab”	“abc”	no	different lengths

2. Why We Need to Check for Isomorphic Strings?

The isomorphic check compares which positions of two strings hold repeated characters, and it ignores the characters themselves. So we use the check whenever the pattern of a text matters more than its letters.

• Word pattern puzzles compare a word against a pattern such as “abba”. A word fits the pattern when the two strings are isomorphic.
• A substitution cipher replaces every letter with another fixed letter, so an encrypted word is always isomorphic to its plain word.
• Coding interviews use the problem to test how well we work with hash maps and arrays.

For example, a cryptogram puzzle app shows the encrypted word “xyyz”. The solver goes through its dictionary and keeps only the words that are isomorphic to “xyyz”, such as “moon”, “deer” and “book”. The words “noon” and “sees” have a different pattern, so the solver skips them. We build that grouping in section 6.2.

3. The Algorithm to Check Isomorphic Strings

The algorithm reads both strings once, from left to right, and remembers the partner of every character it has seen. When a character shows up again with a different partner, the strings are not isomorphic.

The following is a pseudo algorithm.

1. If String1 or String2 is null, or they do not have the same length, return false.
2. For each index i from 0 to length – 1, read the character char1 from String1 and the character char2 from String2.
3. If char1 already has a partner and the partner is not char2, return false.
4. If char2 already has a partner and the partner is not char1, return false.
5. Store char2 as the partner of char1, and char1 as the partner of char2.
6. When the loop ends without a conflict, return true.

Steps 3 and 4 check the two directions. Without step 4, the pair “abc” and “xxy” would return true, as we saw in section 1.

4. Java Example to Check Isomorphic Strings

We write two versions of the algorithm in Java. The first version stores the last position of each character in two int arrays and works only for characters with a code below 256. The second version stores them in two HashMap objects and works for every Unicode character. Both versions run on Java 25.

4.1. Using Two Arrays for ASCII Strings

Let us write a simple Java program to check for isomorphic Strings. The areIsomorphic() method takes two string arguments and determines whether two strings are isomorphic.

public boolean areIsomorphic(String s1, String s2) {

  if (s1 == null || s2 == null
      || s1.length() != s2.length()) {
    return false;
  }

  int[] arr1 = new int[256];
  int[] arr2 = new int[256];

  for (int i = 0; i < s1.length(); i++) {

    char c1 = s1.charAt(i);
    char c2 = s2.charAt(i);

    if (arr1[c1] != arr2[c2]) {
      return false;
    }

    arr1[c1] = i + 1;
    arr2[c2] = i + 1;
  }
  return true;
}

IsomorphicStrings iso = new IsomorphicStrings();
boolean first = iso.areIsomorphic("abbcdd", "qwwcrr");   // true
boolean second = iso.areIsomorphic("aab", "que");        // false

• In the very first step, we make null checks and compare the lengths of the two strings. If their lengths are not equal, they cannot be isomorphic because it will be impossible to have a one-to-one mapping between the characters of both strings.
• The two integer arrays arr1 and arr2 have 256 slots each, one slot per character code from 0 to 255. The size 256 covers the ASCII characters (codes 0 to 127) and the Latin-1 characters (codes 128 to 255).
• Each slot stores the last position (index + 1) where the character was seen, and 0 means “not seen yet”. We iterate over the characters of the strings using a for-loop and check each character pair from s1 and s2.
• The check if (arr1[c1] != arr2[c2]) compares the last positions of c1 and c2. Two partners were always seen together, so their slots hold the same number. Different numbers mean that either c1 was paired with a different character before, or c2 was paired with a different character, so the method returns false.
• If the characters pass the check, both slots get the current position i + 1.
• If the loop completes without finding any mismatch, the strings are isomorphic, and the method returns true.

The array version is fast, but it has one limit. A Java char can hold any code from 0 to 65535, so a character such as the euro sign (code 8364) is outside the arrays.

boolean euro = iso.areIsomorphic("a\u20ACa", "xyx");   // ArrayIndexOutOfBoundsException: Index 8364 out of bounds for length 256

4.2. A Safe Version With Two Maps

When the strings come from users, files or other systems, we cannot assume ASCII. The map version stores the partners in two HashMap objects, forward for the direction from s1 to s2, and backward for the opposite direction. It also reads the strings with codePoints() instead of charAt(), so an emoji, which takes two char values in a Java String, counts as one character.

public static boolean isIsomorphic(String s1, String s2) {
  if (s1 == null || s2 == null) {
    return false;
  }
  int[] cp1 = s1.codePoints().toArray();
  int[] cp2 = s2.codePoints().toArray();
  if (cp1.length != cp2.length) {
    return false;
  }

  Map<Integer, Integer> forward = new HashMap<>();
  Map<Integer, Integer> backward = new HashMap<>();

  for (int i = 0; i < cp1.length; i++) {
    Integer mappedTo = forward.putIfAbsent(cp1[i], cp2[i]);
    Integer mappedFrom = backward.putIfAbsent(cp2[i], cp1[i]);
    if ((mappedTo != null && mappedTo != cp2[i])
        || (mappedFrom != null && mappedFrom != cp1[i])) {
      return false;
    }
  }
  return true;
}

The method putIfAbsent() either stores the new partner and returns null, or keeps the old partner and returns it. So a non-null result that differs from the current character is a conflict. The comparison mappedTo != cp2[i] compares numbers, because Java unboxes the Integer when the other side is a primitive int.

boolean euro = isIsomorphic("a\u20ACa", "xyx");                    // true
boolean emoji = isIsomorphic("\uD83D\uDE00\uD83D\uDE00b", "ccd");   // true (one emoji counts as one character)
boolean caseMatters = isIsomorphic("Aa", "bb");                    // false (A and a are different characters)

A common mistake is to check only the direction from the first string to the second. The method oneWayOnly() below keeps only the forward map, and it gives different answers for the same pair in the two orders.

public static boolean oneWayOnly(String s1, String s2) {
  if (s1 == null || s2 == null || s1.length() != s2.length()) {
    return false;
  }
  Map<Character, Character> forward = new HashMap<>();
  for (int i = 0; i < s1.length(); i++) {
    Character mappedTo = forward.putIfAbsent(s1.charAt(i), s2.charAt(i));
    if (mappedTo != null && mappedTo != s2.charAt(i)) {
      return false;
    }
  }
  return true;
}

boolean wrong = oneWayOnly("abc", "xxy");     // true (wrong)
boolean right = oneWayOnly("xxy", "abc");     // false
boolean fixed = isIsomorphic("abc", "xxy");   // false

5. Performance

The time complexity of both versions is O(n), where n is the length of the string. This is because we need to traverse each character of the strings only once, and an array access or a HashMap lookup takes constant time.

The space complexity of the array version is O(1), or constant space, because the two arrays always have 256 slots, whatever the input size. The map version stores at most one entry per distinct character, so its space is O(k), where k is the number of distinct characters. The map version also reads the code points into two arrays, which adds O(n) space.

	Array version	Map version
Characters	codes 0 to 255 only	every Unicode character
Time	O(n)	O(n)
Extra space	2 x 256 int slots	O(n) for code points, O(k) for maps
Bad input	throws ArrayIndexOutOfBoundsException above code 255	returns true or false

So we use the array version when the input is known to be ASCII, such as in an interview or in a puzzle with the letters a to z. For any other input, the map version is the safe choice.

6. Isomorphic Strings FAQs

6.1. Can a Character Map to Itself?

Yes. The definition only forbids one character having two partners, so c can map to c, as in “abbcdd” and “qwwcrr”. A string is always isomorphic to itself, which is why isIsomorphic(“noon”, “noon”) returns true.

6.2. How Do We Group Isomorphic Strings?

We turn each string into its pattern and group the strings by that pattern. The pattern replaces every character with a number, where the first distinct character gets 0, the second distinct character gets 1, and so on. So “abbcdd” becomes [0, 1, 1, 2, 3, 3], and two strings are isomorphic only when their patterns are equal.

public static List<Integer> pattern(String text) {
  Map<Integer, Integer> firstSeen = new HashMap<>();
  List<Integer> result = new ArrayList<>();
  text.codePoints().forEach(cp -> result.add(firstSeen.computeIfAbsent(cp, k -> firstSeen.size())));
  return result;
}

List<Integer> p1 = pattern("abbcdd");                       // [0, 1, 1, 2, 3, 3]
List<Integer> p2 = pattern("qwwcrr");                       // [0, 1, 1, 2, 3, 3]
boolean isomorphic = pattern("aab").equals(pattern("que"));  // false ([0, 0, 1] vs [0, 1, 2])

With the pattern as the key of a Map, one pass over a word list builds the groups that the cryptogram solver from section 2 needs.

public static Map<List<Integer>, List<String>> groupIsomorphic(List<String> words) {
  Map<List<Integer>, List<String>> groups = new LinkedHashMap<>();
  for (String word : words) {
    groups.computeIfAbsent(pattern(word), k -> new ArrayList<>()).add(word);
  }
  return groups;
}

Map<List<Integer>, List<String>> groups =
    groupIsomorphic(List.of("moon", "deer", "book", "noon", "boob", "sees"));
// {[0, 1, 1, 2]=[moon, deer, book], [0, 1, 1, 0]=[noon, boob, sees]}

6.3. Is the Isomorphic Relation Symmetric?

Yes. If s1 is isomorphic to s2, then s2 is isomorphic to s1, because a one-to-one mapping can be reversed. A method that returns different results for the two orders has a bug, as the oneWayOnly() method in section 4.2 shows.

6.4. What Is the Difference Between Isomorphic Strings and Anagrams?

Anagrams contain the same characters in a different order, such as “listen” and “silent”. Isomorphic strings keep the order but may use different characters. So “listen” and “silent” are anagrams and also isomorphic (every letter appears once in each), whereas “deer” and “book” are isomorphic but not anagrams.

7. Conclusion

Two strings are isomorphic when a one-to-one character mapping turns the first string into the second. The check has to look at both directions, because a one-way check accepts pairs such as “abc” and “xxy”.

The array version with two int[256] arrays is short and fast, but it works only for character codes below 256. The version with two HashMap objects and codePoints() handles every Unicode character and runs in O(n) time as well.

When we need to compare many strings at once, we turn each one into its pattern of numbers and group the strings by pattern.

8. References

• Isomorphic Strings (LeetCode 205)
• HashMap JavaDoc (Java 25)
• String.codePoints() JavaDoc (Java 25))

Happy Learning !!

Source Code on Github