c - 如何降低遍历字符串的时间复杂度？

Question

我正在解决一个问题来查找此类索引的数量，a, b, c, d在字符串中 s , 大小 n仅由小写字母组成，例如:

1 <= a < b < c < d <= n

和

s[a] == s[c] and s[b] == s[d]

我写的代码以一种基本的方式逐个字符地遍历字符串:

#include<stdio.h>

int main()
{
    int n, count = 0;
    char s[2002];
    scanf("%d%s", &n, s);
    for(int a = 0; a<n-3; a++)
    {
        for(int b = a + 1; b<n-2; b++)
        {
            for(int c = b + 1; c<n-1; c++)
            {
                for(int d = c + 1; d<n; d++)
                {
                    if(s[a] == s[c] && s[b] == s[d] && a>=0 && b>a && c>b && d>c && d<n)
                    {
                        count++;
                    }
                }
            }
        }
    }
    printf("%d", count);
    return 0;
}

a、b、c 和 d 是索引。
麻烦的是，如果输入字符串的大小很大，则由于 4 个嵌套循环而超出了时间限制。有什么方法可以改进代码以降低复杂性吗？

The problem statement is available here: https://www.hackerearth.com/practice/algorithms/searching/linear-search/practice-problems/algorithm/holiday-season-ab957deb/

Answer 1

如果您维护一个数组，该数组存储输入字符串中每个字符的累积频率(频率和到目前为止频率分布中的所有频率的总和)，则可以解决该问题。由于字符串仅由小写字符组成，因此数组大小将为 [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 次。我们需要找到所有
pair(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 中的代码。我使用了简单的循环数组，所以它应该很容易理解。

//Input N and string 
//Do not pay attention to the next two lines since they are basically taking 
//input using Java input streams
int N = Integer.parseInt(bufferedReader.readLine().trim());
String str = bufferedReader.readLine().trim();

//Construct an array to store cumulative frequency of each character in the string
int[][] cumulativeFrequency = new int[26][N+1];

//Fill the cumulative frequency array
for (int i = 0;i < str.length();i++)
{
    //character an index i
    char ch = str.charAt(i);

    //Fill the cumulative frequency array for each character 
    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;

//Follow the steps of the algorithm here
for (int i = 0;i < 26;i++)
{
    for (int j = 1; j <= N - 2; j++)
    {
        //Check if character at i is present at index j
        a = cumulativeFrequency[i][j] - cumulativeFrequency[i][j - 1];

        if (a > 0)
        {
            //Check if character at i is present at index k
            for (int k = j + 2; k <= N; k++)
            {
                c = cumulativeFrequency[i][k] - cumulativeFrequency[i][k - 1];

                if (c > 0)
                {
                    //For each character, find b*d
                    for (int l = 0; l < 26; l++)
                    {
                        //For each character calculate b and d
                        b = cumulativeFrequency[l][k-1] - cumulativeFrequency[l][j];
                        d = cumulativeFrequency[l][N] - cumulativeFrequency[l][k];

                        count += b * d;
                        }
                    }
                }
            }
        }
    }

    System.out.println(count);

我希望我帮助了你。 我提供的代码不会给出时间复杂度错误，它适用于所有测试用例 .如果您不理解我的解释中的任何内容，请发表评论。