我的代码需要不同的算法来迭代给定字符串的所有子字符串

Question

所以问题是给出给定字符串中“ab”出现次数等于“ba”出现次数的最长子串的长度。 例如，如果输入是“abba”，则输出应为 4，因为“abba”出现了 1 次“ab”，出现了 1 次“ba”，因此答案为 4。

这是我的代码：

#include <iostream>
using namespace std;

int main()
{
    int t, x;
    string s;
    cin >> t;
    while (t--)
    {
        cin >> x;
        cin >> s;
        int maxlen = 0;
        bool found = false;

        if(x<=2){
            maxlen = 1;
        }
        else {

        for (int i = x; i >= 2; i--)
        {
            for (int j = 0; j <= x - i; j++)
            {
                int ab = 0, ba = 0;
                for (int k = j; k < j + i - 1; k++)
                {
                    if (s[k] == 'a' && s[k + 1] == 'b')
                    {
                        ab++;
                    }
                    else if (s[k] == 'b' && s[k + 1] == 'a')
                    {
                        ba++;
                    }
                }

                if (ab == ba)
                {
                    maxlen = i;
                    found = true;
                    break;
                }
            }
            if (found)
            {
                break;
            }
        }
        }
        cout << maxlen << endl;
    }

    return 0;
}

我只是简单地使用了三重嵌套循环来逐一检查，但这使得时间复杂度为n^3，而这在我最近举办的比赛中没有被接受

我尝试了分离所有子字符串并逐一检查的直接方法，但我需要更优化的代码来降低其时间复杂度

Answer 1

首先，你的算法有一个小错误：

        if(x<=2){
            maxlen = 1;
        }

当

x

为 2 时，结果可能为 2。例如，如果输入是“aa”或“qr”（“ab”或“ba”以外的任何内容），则输出应为 2，而不是 1。所以这个

if

条件应该是

x < 2

而不是

x<=2

。

更高效的算法

您可以在输入字符串的一次迭代中完成此操作。使用“平衡”的概念，表示目前找到的“ab”和“ba”的数量之间的平衡。一开始余额为 0，遇到“ab”时增加它，遇到“ba”时减少它。对于该余额的每个不同值，跟踪您在“第一次”遇到的平衡索引。您可以为此使用数组（但然后向余额添加一些偏移量以避免负索引）。现在，每当您达到之前遇到的平衡时，这两次出现之间的子字符串就是候选解决方案。 这是该算法的实现：

int getMaxLength(std::string s) {
    int n = s.length();
    if (n == 0) return 0;
    int maxLength = 1;
    // Define the balance as some int value that can serve 
    //   as an index in firstOccurrenceOfBalance even if it decreases:
    int balance = n / 2;
    int firstOccurrenceOfBalance[n] = {}; // Initialized with all zeroes
    // We start with a given balance, and thus we have an occurrence of
    //   it at the first position (we use 1-based position)
    firstOccurrenceOfBalance[balance] = 1;
    for (int i = 1; i < n; i++) {
        if (s[i - 1] == 'a' && s[i] == 'b') balance++;
        if (s[i - 1] == 'b' && s[i] == 'a') balance--;
        // If this is the first time we encounter this balance...
        if (firstOccurrenceOfBalance[balance] == 0) {
            // ... then mark the current position as its first occurrence:
            firstOccurrenceOfBalance[balance] = i + 1;
        } else {
            // We had this balance before, so the substring between that first 
            //     occurrence and this one is a potential solution.
            // The "ab" or "ba" we just found is inclusive, so add 2
            maxLength = std::max(maxLength, i + 2 - firstOccurrenceOfBalance[balance]);
        }
    }
    return maxLength;
}

在你的

main

中这样称呼它：

int main() {
    int numTests, strLength;
    std::string s;
    std::cin >> numTests;
    while (numTests--) {
        std::cin >> strLength; // Can be ignored, as we have s.length()
        std::cin >> s;
        int maxLength = getMaxLength(s);
        std::cout << maxLength << std::endl;
    }
    return 0;
}