sequence — максимальная подпоследовательность в переполнении стека

Вопрос:

Где ошибка в моем коде?

Promlem:

Я хотел бы найти максимальную уникальную подпоследовательность в строке. Пример: для aabbaba ответ будет 2 (ab или же ba). Я хотел бы сделать это, повторяя строку только один раз. Разрешены только строчные буквы.

Как указал @hvd, подпоследовательность является уникальной, если все буквы в ней уникальны. В строке может быть одна и та же уникальная подпоследовательность несколько раз.

Подход:

  • начинать с первой буквы строки и повторять до конца
  • напишите позицию буквы в векторе unique, если вы еще не видели письмо
  • увеличить количество для этой подпоследовательности
  • если вы увидели букву, начните новую подпоследовательность. Начните новую подпоследовательность с расстояния от вашей текущей позиции до последнего вхождения. Пример: строка exampletzu, Мы на втором месте. Текущий индекс равен 6. Текущая максимальная подпоследовательность равна 6 (exampl). Перейти к т и создать новую подпоследовательность. Инициировать до 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();
}

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();
}
0

Другие решения

Других решений пока нет …

По вопросам рекламы [email protected]