Counting Equal Pairs in a String in Java

要确定字符串中相等字符对的数量， 请找出文本中相同字符出现在不同位置的所有实例。如果两个字符相同但出现在不同的索引处，则认为该对是“相等”的。目标是确定字符串中存在多少对这样的配对。

理解问题

找出字符串中所有等效但索引不同的字母对。例如，在 字符串“abba”中，字母“a”出现在索引 0 和，这将产生一对相等字符。

符号：将字符串表示为 s。 - 一对表示为 (i, j)，其中 s[i] == s[j]，并且 i< j。

蛮力法

• 最简单的解决方案是使用 嵌套循环。
• 外层循环遍历字符串中的每个字符。
• 内层循环搜索所有连续字符之间的匹配项。

此技术的时空复杂度为 O(n^2)，其中 n 是字符串的长度。

示例 1：“Abba”

1. 输入“abba”。
2. 对
   
   • 将索引 0 处的字符（'a'）与后续索引（1、2、3）处的字符进行比较。
     
     1. 索引零处的“a”和索引一处的“b”不相等。
     2. 索引零处的“a”和索引二处的“b”不相等。
     3. 索引 0 处的“a”和索引 3 处的“a”构成一对相等字符。
   • 将索引 1 处的字符（'b'）与后续索引进行比较
     
     1. 索引 1 处的“b”和索引 2 处的“b”构成一对相等字符。
     2. 索引一处的“b”和索引三处的“a”不相等。
   • 将索引 2 处的字符（'b'）与后续索引进行比较
     
     1. 索引二处的“b”和索引三处的“a”不相等。
3. 结果：有两个相等对：(0, 3) 和 (1, 2)。

示例 2：“abcd”

1. 输入“abcd”。
2. 对
   
   • 索引 0 处的“a”与后续索引不匹配。
   • 索引 1 处的“b”与连续索引不匹配。
   • 索引 2 处的“c”与任何后续索引都不匹配。
   • 索引 3 处的“d”之后没有连续字符。
3. 因此，没有配对是等效的。

文件名：EqualPairs.java

输出

 
2   

使用 HashMap 的优化方法

由于其二次时空复杂度，暴力方法对于大型字符串可能效率低下。我们可以通过使用 hashmap（或字典）在遍历字符串时监控每个字符的出现次数来改进它。此方法的工作原理如下

1. 创建一个存储每个字符计数的字典。
2. 遍历字符串，同时更新字典。
3. 将每个字符的计数（到目前为止看到的）添加到对的总计数中。

此方法的时空复杂度降至 O(n)。

文件名：EqualPairsOptimized.java

输出

 
2   

结论

计算字符串中的相等字符对需要找到不同索引处的所有字符匹配项。对于短字符串，暴力方法效果很好，但对于较长的字符串，使用哈希图的改进方法更有效。理解这两种策略可以让你根据情况和要求选择最佳策略。