Вопрос:
Где ошибка в моем коде?
Promlem:
Я хотел бы найти максимальную уникальную подпоследовательность в строке. Пример: для aabbaba
ответ будет 2 (ab
или же ba
). Я хотел бы сделать это, повторяя строку только один раз. Разрешены только строчные буквы.
Как указал @hvd, подпоследовательность является уникальной, если все буквы в ней уникальны. В строке может быть одна и та же уникальная подпоследовательность несколько раз.
Подход:
unique
, если вы еще не видели письмоexampletzu
, Мы на втором месте. Текущий индекс равен 6. Текущая максимальная подпоследовательность равна 6 (exampl
). Перейти к т и создать новую подпоследовательность. Инициировать до 7 (xamplet
). Код:
#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();
}
При обновлении 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();
}
Других решений пока нет …