Increasing Substring Solution Google Kickstart 2021

Table of Contents

Problem

Your friend John just came back from vacation, and he would like to share with you a new property that he learned about strings.

John learned that a string CC of length LL consisting of uppercase English characters is strictly increasing if, for every pair of indices ii and jj such that 1≤i<j≤L1≤i<j≤L (11-based), the character at position ii is smaller than the character at position jj.

For example, the strings ABC and ADF are strictly increasing, however the strings ACC and FDA are not.

Now that he taught you this new exciting property, John decided to challenge you: given a string SS of length NN, you have to find out, for every position 1≤i≤N1≤i≤N, what is the length of the longest strictly increasing substring that ends at position ii.

Input

The first line of the input gives the number of test cases, TT. TT test cases follow.

Each test case consists of two lines.

The first line contains an integer NN, representing the length of the string.

The second line contains a string SS of length NN, consisting of uppercase English characters.

Output

For each test case, output one line containing Case #xx: y1y1 y2y2 ... ynyn, where xx is the test case number (starting from 1) and yiyi is the length of the longest strictly increasing substring that ends at position ii.

Limits

Memory limit: 1 GB.
1≤T≤1001≤T≤100.

Test Set 1

Time limit: 20 seconds.
1≤N≤1001≤N≤100.

Test Set 2

Time limit: 40 seconds.
1≤N≤2×1051≤N≤2×105.

Sample

Sample Input

2
4
ABBC
6
ABACDA

Sample Output

Case #1: 1 2 1 2
Case #2: 1 2 1 2 3 1

In Sample Case #1, the longest strictly increasing substring ending at position 11 is A. The longest strictly increasing substrings ending at positions 22, 33 and 44 are AB, B and BC, respectively.

In Sample Case #2, the longest strictly increasing substrings for each position are A, AB, A, AC, ACD and A.1

Also Read:

Solution:

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ff first
#define ss second
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int N = 1000005;
const ll MOD = 1000000007;
const ll INF = 0x3f3f3f3f3f3f3f3f;

char a[N];

void go(){
int n;
cin>>n;
int k = 0;
a[0] = ‘A’ – 1;
for(int i = 1; i <= n; ++i){ cin>>a[i];
if(a[i] > a[i – 1]){
++k;
cout<<k<<‘ ‘;
} else {
k = 1;
cout<<k<<‘ ‘;
}
}
cout<<‘\n’;
}

int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);

int tt;

cin>>tt;

for(int i = 1; i <= tt; ++i)

{

cout<<“Case #”<<i<<“: “;

go();

}

Increasing Substring Solution Google Kickstart 2021