Una posible solución:
#include <iostream>
int main( ) {
int count;
int length;
char *string = nullptr;
std::cin >> count;
for( int n = 0; n < count; ++n ) {
std::cin >> length;
string = new char[length + 1];
string[length] = 0;
std::cin >> string;
const char *start = string;
int sublen = 0;
while( *start ) {
++sublen;
const char *curr = start + 1;
while( ( *curr ) && ( *curr >= *( curr - 1 ) ) ) {
++sublen;
++curr;
}
++start;
}
std::cout << "Combinaciones: " << sublen << '\n';
delete[] string;
}
return 0;
}
Me parecía divertido, así que no me baso en tu código; está escrito desde 0.
No lo he cronometrado, pero creo que tarda menos de 1 seg. en ejecutarse. Y si usaramosañadieramos un poco de gestión extra de memoria (o usáramos std::string
, que reutiliza el buffer de memoria si le es posible, como te indican en los comentarios) aun tardaría menos :-)
Compilado con g++ -std=c++11 -Wall -Wextra -pedantic
.