如果您维护一个数组,该数组存储输入字符串中每个字符的累积频率(频率分布中频率和到目前为止所有频率的总和),则可以解决此问题。由于字符串只包含小写字符,因此数组大小将为[26][N+1]
。
例如:
index - 1 2 3 4 5
string - a b a b a
cumulativeFrequency array:
0 1 2 3 4 5
a 0 1 1 2 2 3
b 0 0 1 1 2 2
我通过将输入字符串的第一个字符的索引设置为1来创建了该数组。这样做将有助于我们稍后解决问题。现在,只需忽略列0,并假设字符串从索引1而不是0开始。
有用的信息
使用累积频率数组,我们可以轻松地检查一个字符是否存在于任何索引i处:
if cumulativeFrequency[i]-cumulativeFrequency[i-1] > 0
从i到j范围内(不包括i和j)字符出现的次数:
frequency between i and j = cumulativeFrequency[j-1] - cumulativeFrequency[i]
算法
1: for each character from a-z:
2: Locate index a and c such that charAt[a] == charAt[c]
3: for each pair (a, c):
4: for character from a-z:
5: b = frequency of character between a and c
6: d = frequency of character after c
7: count += b*d
时间复杂度
第1-2行:
最外层循环将运行26次。我们需要找到所有的(a, c)组合,为此我们需要O(n^2)的时间复杂度。
第3-4行:
对于每个组合,我们再次运行一个循环26次,以检查在a和c之间以及c之后每个字符出现的次数。
第5-7行:
使用累积频率数组,对于每个字符,我们可以在O(1)的时间内轻松计算它在a和c之间以及c之后出现的次数。
因此,总体复杂度为 O(26*n^2*26)
= O(n^2)
。
代码
我用Java编写代码。我没有C语言的代码。我使用了简单的循环和数组,因此应该很容易理解。
int N = Integer.parseInt(bufferedReader.readLine().trim());
String str = bufferedReader.readLine().trim();
int[][] cumulativeFrequency = new int[26][N+1];
for (int i = 0;i < str.length();i++)
{
char ch = str.charAt(i);
for (int j = 0;j < 26;j++)
{
cumulativeFrequency[j][i+1] += cumulativeFrequency[j][i];
if (ch-97 == j) cumulativeFrequency[j][i+1]++;
}
}
int a, b, c, d;
long count = 0;
for (int i = 0;i < 26;i++)
{
for (int j = 1; j <= N - 2; j++)
{
a = cumulativeFrequency[i][j] - cumulativeFrequency[i][j - 1];
if (a > 0)
{
for (int k = j + 2; k <= N; k++)
{
c = cumulativeFrequency[i][k] - cumulativeFrequency[i][k - 1];
if (c > 0)
{
for (int l = 0; l < 26; l++)
{
b = cumulativeFrequency[l][k-1] - cumulativeFrequency[l][j];
d = cumulativeFrequency[l][N] - cumulativeFrequency[l][k];
count += b * d;
}
}
}
}
}
}
System.out.println(count);
我希望我已经对你有所帮助。我提供的代码不会引起时间复杂度错误,并且它将适用于所有测试案例。如果我的解释有什么你不明白的地方,请在评论区留言。
O(n^2)
。 - AKSingh