Question:
Repl link:
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
string listByValue(string input) {
int n = input.length();
vector<char> letters;
vector<int> values(n);
// Process the letters from left to right
for (int i = 0; i < n; i++) {
char letter = input[i];
int value;
// Find the index where the letter should be inserted in alphabetical order
int index = lower_bound(letters.begin(), letters.end(), letter) - letters.begin();
if (index == letters.size() || letters[index] != letter) {
// If the letter is not already in the array, insert it at the found index
letters.insert(letters.begin() + index, letter);
// Assign the value based on the rules
if (index == 0) {
value = 0;
} else if (index == letters.size() - 1) {
value = values[i-1] + 1;
} else {
value = max(values[i-1], values[i-2]) + 1;
}
} else {
// If the letter is already in the array, insert the new letter before the existing one
letters.insert(letters.begin() + index, letter);
// Assign the same value as the existing letter
value = values[i-1];
}
values[i] = value;
}
// Concatenate the letters in order of their value
string result;
for (int i = 0; i <= *max_element(values.begin(), values.end()); i++) {
for (int j = 0; j < n; j++) {
if (values[j] == i) {
result += letters[j];
}
}
}
return result;
}
int main()
{
ofstream fout("output.txt");
string input;
getline(cin, input);
string result = listByValue(input);
fout << result << "\n";
fout.close();
return 0;
}