Count Isomorphic Substring Pairs
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.
countIsomorphicSubstringPairs(S: string, P: string) that takes two strings, S and P, as input.(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.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".)S: A string consisting of lowercase English letters.P: A string consisting of lowercase English letters.number representing the total count of isomorphic substring pairs.S or P is empty, the count should be 0.Examples
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.
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.
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
1 <= S.length, P.length <= 2000S and P consist only of lowercase English letters ('a'-'z').O(N^2 + M^2) where N, M are string lengths).Loading editor...