In today's globalized society, Xiao Guai's parents want him to immerse himself in an English-speaking environment from an early age. At the age of five, Xiao Guai's kindergarten teacher is training everyone to recite the English alphabet A to Z in order. Xiao Guai can quickly memorize all 26 letters, but he always gets the order wrong. The teacher noticed that other children also had this problem, so she prepared a test. The test includes a long string of English letters, and the children are asked to find the longest substring arranged in alphabetical order and write down its length. For example, in the string "abcwkodvwxyzwia", "abc" and "vwxyz" are arranged in alphabetical order. The longest substring is "vwxyz", with a length of 5. The teacher has now generated some random strings. Please help write a solution so that the children can enjoy learning English!
※ Note: Reversed strings do not count. For example, "zyxab" only "ab" meets the condition of being arranged in alphabetical order.
Sample Inputs/Outputs
| Sample Input(s) | Sample Output(s) |
|---|---|
| The input has only one line, N, which is a string consisting of lowercase letters. (0 < N.length() < 10000) | Output a positive integer M (1 <= M <= N) representing the length of the longest ordered substring, followed by a string of length M representing the longest ordered substring, without newline characters. If there are multiple substrings of maximum length, output the last occurrence. If there are no adjacent letters arranged in alphabetical order, then the length of the longest-ordered substring is 1. |
| abcwkodvwxyzwia | 5 vwxyz |
| gfeabuvstyzijo | 2 ij |
| apple | 1 e |
Thought Process
Use ASCII codes to check if letters are consecutive. Run a for loop over the string, and for each position, run an inner loop from the current position + 1 to the end. If consecutive letters are found, add them continuously to a temporary string until a break occurs in the sequence. Then compare the length with the longest string, and if it's greater than or equal to, set the answer string as the new string.
Sample Code－ZeroJudge E837: Letters
#include <iostream>
using namespace std;
int main() {
cin.sync_with_stdio(0);
cin.tie(0);
string str, ans = "";
cin >> str;
for (int i = 0; i<str.length(); i++)
{
string tmp = "";
tmp += str[i];
int count = int(str[i]);
for (int j = i+1; j<str.length(); j++)
{
if (int(str[j]) == count + 1)
{
count++;
tmp += str[j];
}
else break;
}
if (tmp.length() >= ans.length()) ans = tmp;
}
cout << ans.length() << " " << ans << "\n";
}
//ZeroJudge E837
//Dr. SeanXD