统计同构子字符串的数目问题（进阶版）

题目描述

给定一个字符串s，我们需要统计所有同构子字符串的数目。同构字符串定义为：如果可以通过对另一个字符串进行字符替换（所有相同字符必须替换为相同字符，不同字符必须替换为不同字符）得到，则两个字符串是同构的。

例如：

• "egg" 和 "add" 是同构的（e→a, g→d）
• "foo" 和 "bar" 不是同构的（o需要同时映射到a和r）
• "paper" 和 "title" 是同构的（p→t, a→i, e→l, r→e）

进阶要求：统计s中所有满足同构性质的子字符串的个数。

解题思路

这个问题可以通过区间动态规划来解决。我们需要判断任意区间[i, j]的子串是否同构，并统计所有满足条件的区间。

关键观察：一个字符串是同构的，当且仅当它的字符出现模式是唯一的。也就是说，对于字符串中每个位置k，第一个出现该字符的位置应该相同。

动态规划定义

定义dp[i][j]表示子串s[i...j]是否同构（true/false）。

状态转移方程

1. 基本情况：长度为1的子串总是同构的

   • dp[i][i] = true (对于所有i)

2. 基本情况：长度为2的子串

   • dp[i][i+1] = true 当且仅当 s[i] ≠ s[i+1]

3. 一般情况：对于长度>2的子串s[i...j]

   • dp[i][j] = true 当且仅当满足以下两个条件：
     a) dp[i+1][j-1] = true（内部子串同构）
     b) 字符映射关系一致：
     • 如果s[i] == s[j]，则要求内部子串中s[i]和s[j]的映射关系一致
     • 如果s[i] ≠ s[j]，则要求这两个字符在内部子串中的首次出现位置模式匹配

具体实现步骤

def count_isomorphic_substrings(s):
    n = len(s)
    if n == 0:
        return 0
    
    # dp[i][j]表示s[i...j]是否同构
    dp = [[False] * n for _ in range(n)]
    count = 0
    
    # 基本情况：长度为1的子串
    for i in range(n):
        dp[i][i] = True
        count += 1
    
    # 基本情况：长度为2的子串
    for i in range(n-1):
        if s[i] != s[i+1]:
            dp[i][i+1] = True
            count += 1
    
    # 长度从3到n
    for length in range(3, n+1):
        for i in range(n-length+1):
            j = i + length - 1
            
            # 检查内部子串是否同构
            if not dp[i+1][j-1]:
                continue
            
            # 检查字符映射关系
            if is_isomorphic_pattern(s, i, j):
                dp[i][j] = True
                count += 1
    
    return count

def is_isomorphic_pattern(s, i, j):
    """检查子串s[i...j]的字符映射关系是否一致"""
    # 创建字符到首次出现位置的映射
    first_occurrence = {}
    
    for k in range(i, j+1):
        if s[k] not in first_occurrence:
            first_occurrence[s[k]] = k - i  # 相对位置
    
    # 检查模式是否一致
    pattern = tuple(first_occurrence[char] for char in s[i:j+1])
    
    # 简化检查：只需要验证首尾字符的映射关系
    if s[i] == s[j]:
        # 首尾字符相同，需要确保内部映射一致
        return check_internal_mapping(s, i, j)
    else:
        # 首尾字符不同，需要确保它们的首次出现位置模式匹配
        return first_occurrence[s[i]] == 0 and first_occurrence[s[j]] == j-i

def check_internal_mapping(s, i, j):
    """检查当首尾字符相同时的内部映射关系"""
    # 简化的检查：确保没有冲突的字符映射
    char_map = {}
    for k in range(i, j+1):
        if s[k] not in char_map:
            # 检查这个字符是否应该映射到已存在的模式
            for existing_char, pattern in char_map.items():
                if (k == i and existing_char == s[j]) or (k == j and existing_char == s[i]):
                    if pattern != char_map.get(s[k], -1):
                        return False
            char_map[s[k]] = len(char_map)
    
    return True

优化版本

上面的实现可以进一步优化，避免重复计算：

def count_isomorphic_substrings_optimized(s):
    n = len(s)
    count = 0
    
    # 对于每个起始位置，使用更高效的模式检查
    for i in range(n):
        # 记录字符的首次出现位置（相对位置）
        pattern_map = {}
        current_pattern = []
        
        for j in range(i, n):
            if s[j] not in pattern_map:
                pattern_map[s[j]] = len(pattern_map)
            current_pattern.append(pattern_map[s[j]])
            
            # 检查当前模式是否有效（简化检查）
            if is_valid_pattern(current_pattern):
                count += 1
    
    return count

def is_valid_pattern(pattern):
    """检查模式是否有效（简化的同构检查）"""
    # 基本检查：模式应该满足同构性质
    # 这里可以使用更复杂的检查，但为了效率我们简化
    return len(set(pattern)) == max(pattern) + 1 if pattern else True

算法复杂度分析

• 时间复杂度：O(n³) - 三层循环
• 空间复杂度：O(n²) - DP表格存储

实际应用

这个算法可以用于：

1. 字符串模式分析
2. 生物信息学中的序列比较
3. 代码克隆检测
4. 数据压缩中的模式识别

通过这种方法，我们可以高效地统计字符串中所有同构子字符串的数目。