In this Leetcode Counting Strings problem solution, Alice got a message M. It is in an alien language. A string in an alien language is said to be valid if it contains the letter a or z. Alice decided to count the number of valid substrings of the message M. Help him to do this. Two substrings are different if it occurs at different positions in the message.


HackerEarth Counting Strings problem solution


HackerEarth Counting Strings problem solution.

T = int(input())

for _ in range(T):

    def nextOccurrence(M, n, start, ch1, ch2):

        for i in range(start, n):

            if (M[i] == ch1 or M[i] == ch2):

                return i

        return -1
    def countSubStr(M, n, ch1, ch2):

        cnt = 0

        j = nextOccurrence(M, n, 0, ch1, ch2)

        for i in range(n):

            while (j != -1 and j < i):
                j = nextOccurrence(M, n, j + 1, ch1, ch2)

            if (j == -1):

                break

            cnt += (n - j)

        return cnt

    M = str(input())
    n = len(M)
    ch1 = "a"
    ch2 = "z"
    print(countSubStr(M, n, ch1, ch2))