技术问询：计算移除字符串中所有“he”“lo”子串的最大成本

问题描述 #

给定字符串S，以及两个整数P（移除子串"he"的得分）和Q（移除子串"lo"的得分），每次移除指定子串后，剩余字符会自动拼接（可能生成新的可移除子串）。要求计算通过移除所有可匹配的"he"和"lo"子串能获得的最大总得分。

示例：当S = 'hellohellohellohellohello'，P = 6，Q = 4时，总得分是50。

核心思路 #

移除顺序直接影响最终得分，优先处理得分更高的子串是最优策略：

• 如果移除"he"的得分P更高，先彻底移除所有"he"（包括移除后新生成的），再处理"lo"；
• 如果移除"lo"的得分Q更高，则反之。
  这种策略能确保每一步都获取当前最大可能的得分，避免因先处理低分子串而破坏高分子串的形成。

实现方案（Python） #

用栈结构处理字符串，栈适合跟踪最近的字符，方便检查是否形成目标子串：

def max_total_score(S, P, Q):
    # 确定优先处理的子串和对应得分
    if P >= Q:
        first_target, first_points = "he", P
        second_target, second_points = "lo", Q
    else:
        first_target, first_points = "lo", Q
        second_target, second_points = "he", P
    
    total = 0
    # 第一步：处理优先子串
    stack = []
    for char in S:
        stack.append(char)
        # 检查栈顶两个字符是否匹配优先子串
        if len(stack) >= 2 and ''.join(stack[-2:]) == first_target:
            stack.pop()
            stack.pop()
            total += first_points
    
    # 第二步：处理剩余字符串中的次优先子串
    remaining_str = ''.join(stack)
    stack = []
    for char in remaining_str:
        stack.append(char)
        if len(stack) >= 2 and ''.join(stack[-2:]) == second_target:
            stack.pop()
            stack.pop()
            total += second_points
    
    return total

# 验证示例
if __name__ == "__main__":
    S = 'hellohellohellohellohello'
    P = 6
    Q = 4
    print(max_total_score(S, P, Q))  # 输出：50

示例验证 #

示例中的S是5个"hello"拼接：

1. 优先处理得分更高的"he"：每个"hello"含1个"he"，5次移除得5*6=30分，剩余字符串为5个"llo"拼接；
2. 再处理"lo"：每个剩余的"llo"含1个"lo"，5次移除得5*4=20分；
3. 总得分30+20=50，与示例结果一致。

内容的提问来源于stack exchange，提问作者Rohit R.K.