algorithm - Count lexographically sorted substrings -

given string s of length n. string s made of lower case english alphabets. need counthow many substrings of s sorted.

given string s, need count number of sorted substrings of s.

a string s lexicographically sorted if s[i] ≤ s[i+1] 1 ≤ ≤ n-1 (consider 1-based indexing).

example : let string s="bba" answer 4

explanation : substrings of 'bba' are: b, b, a, bb, ba, bba out of these 6 substrings, 4 ('b', 'b', 'a' , 'bb') substrings sorted. answer 4.

my current solution no better brute force . check each substring , check if sorted or not. string length can 1000000 o(n^2) approach won't work out. can better solution problem ?

make 2 indexes - left , right. set them both first symbol index of string. increment right while s[right] ≤ s[right+1].
when next symbol violates order, have substring ss = s[left..right], substrings of ss sorted too.
find number through ss length:

k = right - left + 1 

you have k one-char substrings, k-1 two-char ones... , 1 k-length substring.

n = 1 + 2 +... + k = k * (k + 1) / 2 

add n overall number of susbstrings, move left , right (right + 1) , continue.