Join Regular Classroom : Visit ClassroomTech

Increasing Substring – Google Kickstart 2021 Round B – Solve

/ Miscellaneous / By

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 C of length L consisting of uppercase English characters is strictly increasing if, for every pair of indices i and j such that 1≤i<j≤L (1-based), the character at position i is smaller than the character at position j.

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 S of length N, you have to find out, for every position 1≤i≤N, what is the length of the longest strictly increasing substring that ends in position i.


Input format: The first line of the input gives the number of test cases, T. T test cases follow.

Each test case consists of two lines.

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

The second line contains a string S of length N, consisting of uppercase English characters.

Output format: For each test case, output one line containing Case #x: y1 y2 ... yn, where x is the test case number (starting from 1) and y[i] is the length of the longest strictly increasing substring that ends at position i.

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 Input:

2
4
ABBC
6
ABACDA

Sample Output: 

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

Explanation: In Sample Case #1, the longest strictly increasing substring ending at position 1 is A. The longest strictly increasing substrings ending at positions 2, 3 and 4 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.

Solution: We strongly recommend you to try the problem first before moving to the solution.

C++

/* C++ solution for Increasing Substring */
/* Google Kickstart Round B - 2021 Problem A solution by CodeWindow */
/* www.codewindow.in */

#include <bits/stdc++.h>
using namespace std;

void solve() {
    int n, count;
    string s;
    cin >> n;
    cin >> s;
    for(int i=0; i<n; i+=count) {   // increment i by count
        count=1;   // Initialize count by 1 every time
        for(int j=i; j<n; ++j) {
            if(s[j+1]>s[j]) {   // If condition satisfies then count it
                cout << count << " ";   // Print the count as well for each
                ++count;
            }
            else{
                cout << count << " ";  
                break;   // Else print the count and break the loop
            } 
        }
    }
    cout << "\n";
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	int t=1;
	cin >> t;   // Input the testcase
	for(int i=0; i<t; ++i) {
	    cout << "Case #" << i+1 << ": ";   // Output format given by Google
	    solve();
	}
	return 0;
}

Input:

2
4
ABBC
6
ABACDA

Output:

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

Proof of execution

Register for Google Kick Start 2021

Follow Us

You Missed