Frontend School

Count Isomorphic Substring Pairs

DSA
hard

Count Isomorphic Substring Pairs

Hard
String
Hashing
Two Pointers

Overview

In modern data processing, identifying structural similarities between data sequences is crucial. This problem focuses on finding "isomorphic" relationships between substrings of two given strings. Two substrings are isomorphic if one can be transformed into the other by consistently replacing each character with another character, maintaining the pattern of character occurrences. Your task is to count the total number of pairs of substrings, one from each input string, that exhibit this isomorphic property.

What you need to do / Task

  1. Implement a function countIsomorphicSubstringPairs(S: string, P: string) that takes two strings, S and P, as input.
  2. Your function should identify all pairs of substrings (sub_S, sub_P) such that sub_S is a substring of S, sub_P is a substring of P, sub_S and sub_P have the same length, and they are isomorphic.
  3. Two strings s1 and s2 are considered isomorphic if for any two indices k1 and k2 within their bounds:
    • s1[k1] == s1[k2] if and only if s2[k1] == s2[k2]. (This means they have the same "pattern" of character occurrences, even if the actual characters are different. For example, "aba" and "cdc" are isomorphic, as are "abc" and "xyz".)
  4. Return the total count of such isomorphic substring pairs.

Input & output

  • S: A string consisting of lowercase English letters.
  • P: A string consisting of lowercase English letters.
  • Returns: A number representing the total count of isomorphic substring pairs.

Clarifications

  • A substring is defined by its starting and ending indices. For example, in "banana", "ana" appears twice (at index 1 and index 3). These are considered distinct substrings for the purpose of pair counting.
  • Substrings of length 1 are always isomorphic. E.g., "a" is isomorphic to "b".
  • If S or P is empty, the count should be 0.

Examples

1

Example 1

Input:

S = "aba", P = "cdc"

Output:

14

Note:

For S="aba": substrings are "a" (3 times), "b" (1 time), "ab" (1 time), "ba" (1 time), "aba" (1 time). Their canonical forms are '0', '0', '0', '01', '01', '010' respectively. For P="cdc": substrings are "c" (3 times), "d" (1 time), "cd" (1 time), "dc" (1 time), "cdc" (1 time). Their canonical forms are '0', '0', '0', '01', '01', '010' respectively.

Canonical forms and counts for S: {'0': 3, '01': 2, '010': 1} Canonical forms and counts for P: {'0': 3, '01': 2, '010': 1}

Matching pairs: '0': 3 (from S) * 3 (from P) = 9 '01': 2 (from S) * 2 (from P) = 4 '010': 1 (from S) * 1 (from P) = 1 Total = 9 + 4 + 1 = 14.

2

Example 2

Input:

S = "abc", P = "def"

Output:

14

Note:

For S="abc": Canonical forms and counts: {'0': 3, '01': 2, '012': 1} For P="def": Canonical forms and counts: {'0': 3, '01': 2, '012': 1}

Matching pairs: '0': 3 * 3 = 9 '01': 2 * 2 = 4 '012': 1 * 1 = 1 Total = 9 + 4 + 1 = 14.

3

Example 3

Input:

S = "banana", P = "orange"

Output:

65

Note:

For S="banana": '0': 6 times (for 'b', 'a' at idx 1, 'n' at idx 2, 'a' at idx 3, 'n' at idx 4, 'a' at idx 5) '01': 5 times (for 'ba', 'an' (idx 1), 'na' (idx 2), 'an' (idx 3), 'na' (idx 4)) '010': 3 times (for 'ana' (idx 1), 'nan' (idx 2), 'ana' (idx 3)) '012': 1 time (for 'ban') '0101': 2 times (for 'anan' (idx 1), 'nana' (idx 2)) '0121': 1 time (for 'bana') '01010': 1 time (for 'anana') '01212': 1 time (for 'banan') '012121': 1 time (for 'banana')

For P="orange" (all unique characters): '0': 6 times '01': 5 times '012': 4 times '0123': 3 times '01234': 2 times '012345': 1 time

Matching canonical forms: '0': 6 (from S) * 6 (from P) = 36 '01': 5 (from S) * 5 (from P) = 25 '012': 1 (from S) * 4 (from P) = 4 Other canonical forms from S (e.g., '010') do not appear in P. Other canonical forms from P (e.g., '0123') do not appear in S. Total = 36 + 25 + 4 = 65.

Constraints

Constraints & assumptions

  • 1 <= S.length, P.length <= 2000
  • S and P consist only of lowercase English letters ('a'-'z').

What interviewers evaluate

  • Correctness: The solution accurately identifies and counts all isomorphic substring pairs according to the problem definition.
  • Efficiency: The algorithm runs within acceptable time and space complexity bounds for the given constraints (ideally O(N^2 + M^2) where N, M are string lengths).
  • Code Quality: The code is well-structured, readable, and follows best practices (e.g., clear variable names, modularity).
  • Algorithm Design: Demonstrates a clear understanding of string algorithms and data structures, specifically how to efficiently compare string patterns (e.g., using canonical forms and polynomial hashing).
  • Edge Cases: Handles edge cases such as single-character strings and strings with repeating characters correctly.

Loading editor...