北京海淀区信息学竞赛 · 2023 北京市海淀区信息学竞赛（初赛）试题 第 12 题

定义一种字符串操作，一次可以将其中一个元素移到任意位置。举例说明，对于字符串 $\tt{BCA}$ 可以将 $\tt{A}$ 移到 $\tt{B}$ 之前，变成字符串 $\tt{ABC}$。如果要将字符串 $\tt{DACHEBGF}$ 变成 $\tt{ABCDEFGH}$ 最少需要（ ）次操作。

本题考查字符串处理相关知识，包括子串的概念、字符串函数的使用等。

常见误区：计算子串时遗漏重复子串，区分不清子串（连续）和子序列（可不连续）。

核心概念：子串是字符串中任意一段连续字符组成的新字符串；长度为n的字符串有n(n+1)/2个非空子串。

推导分析：子串总数 = n(n+1)/2；strcat()用于字符串拼接，strlen()返回字符串长度。

避坑指南：含重复字符的字符串，不同子串数少于理论最大值。

解题技巧：用双指针法枚举所有子串，注意去重。