SGRSTR - Editorial

PROBLEM LINK:

Practice
Contest
Author: Vatsal Kanakiya
Tester: Dipen Ved
Editorialist: Lakshmi

DIFFICULTY:

EASY

PREREQUISITES:

Strings and basic concepts of modulo.

PROBLEM:

You are given a string S of length N , you have to find the number of substrings of S which are also a substring of string …abcdefghijklmnopqrstuvwxyz…
i.e the english alphabets which are infinite on both the ends.

QUICK EXPLANATION:

In the given string S we will find whether the consecutive characters are arranged in continuous lexographic order.

EXPLANATION:

The main logic is that we are considering 2 consecutive characters of the given string at a time and comparing it with the english alphabets.
count is set to 0 and len is set to 1.
First we will start the for loop from the second character of the string and it will be iterated till the last character of the string.
If the second character and the first character are the substring of …abcdefghijklmnopqrstuvwxyz… i.e they are consecutive characters of english alphabets then variable len will be incremented by 1.
Else (len+1).len/2
is added to count and len will be set to 1 again.
That means len will be increemented till we are getting substrings of …abcdefghijklmnopqrstuvwxyz… and once it is not a substring len is again set to 1 and it will start checking for the next character.
This will be continued till the last character and second last character of the given string is compared.
Then outside the for loop (len+1)*len)/2 is added agin to count and count is printed.

AUTHOR’S AND TESTER’S SOLUTIONS:

Solution can be found here.