c++ - C++中的最大子序列

Question

问题:

我的代码哪里出错了？

问题:

我想在字符串中找到最大的唯一子序列。示例:对于 aabbaba，答案为 2(ab 或 ba)。我想通过只迭代字符串一次来做到这一点。只允许使用小写字母。

正如@hvd 所指出的，如果子序列中的所有字母都是唯一的，那么它就是唯一的。字符串中可以多次出现相同的唯一子序列。

方法:

• 从字符串的第一个字母开始，迭代结束
• 写下字母在 vector 中出现的位置 unique，如果你还没有看到字母的话
• 增加这个子序列的计数
• 如果你看到了这封信，开始一个新的子序列。使用从当前位置到最后一次出现的距离初始化新的子序列。示例:字符串是 exampletzu。我们在第二个e。当前索引为 6。当前最大子序列为 6 (exampl)。转到 t 并创建一个新的子序列。将其初始化为 7 (xamplet)。
• 你知道你可以中止，如果当前子序列等于 26，因为这是可能的最大值

代码:

#include <iostream>
#include <vector>
#include <algorithm>
//#include <bits/stdc++.h>
#include <string>

using namespace std;

int main(int argc, char *argv[])
{
    typedef vector<int>::iterator it;

    int length = 7;
    string p = "aabbaba";
    // result
    vector<int> max(length, 0);
    int subSeq = 0;

    // alphabet
    vector<int> unique(26, -1);
    bool flag = false;
    for (int i = 0; i < length; ++i)
    {
        int pos = (p[i] - 97) % 26;
        if (unique[pos] != -1)
        {
            // letter already existed. Start new max
            ++subSeq;
            max[subSeq] = i - unique[pos] - 1;
            for (int j = 0; j < unique.size(); ++j)
            {
                if (unique[j] != -1)
                {
                    unique[j] = unique[pos];
                }
            }
        }
        ++max[subSeq];
        if (max[subSeq] == 26)
        {
            flag == true;
            break;
        }
        unique[pos] = i;
    }

    int result = 0;
    if (!flag)
    {
        for (it i = max.begin(); i != max.end(); ++i)
        {
            if (*i > result)
            {
                result = *i;
            }
        }
    }
    else
    {
        result = 26;
    }
    cout << result << endl;
    cout.flush();
     }

Answer 1

当你更新 unique 时，你应该保留那些自 unique[pos] 以来已经出现的字母:

#include <iostream>
#include <vector>
#include <algorithm>
//#include <bits/stdc++.h>
#include <string>

using namespace std;

int main(int argc, char *argv[])
{
    typedef vector<int>::iterator it;

    p = argv[1];
    length = p.length();
    // result
    vector<int> max(length, 0);
    int subSeq = 0;

    // alphabet
    vector<int> unique(26, -1);
    bool flag = false;
    for (int i = 0; i < length; ++i)
    {
        int pos = (p[i] - 97) % 26;
        if (unique[pos] != -1)
        {
            // letter already existed. Start new max
            ++subSeq;
            max[subSeq] = i - unique[pos] - 1;
            for (int j = 0; j < unique.size(); ++j)
            {
                if (unique[j] != -1)
                {
          if (unique[j] < unique[pos]) {
                    unique[j] = unique[pos];
          }
                }
            }
        }
        ++max[subSeq];
        if (max[subSeq] == 26)
        {
            flag == true;
            break;
        }
        unique[pos] = i;
    }

    int result = 0;
    if (!flag)
    {
        for (it i = max.begin(); i != max.end(); ++i)
        {
            if (*i > result)
            {
                result = *i;
            }
        }
    }
    else
    {
        result = 26;
    }
    cout << result << endl;
    cout.flush();
     }