Alice got a message M. It is in an alien language. A string in an alien language is said…
- User
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. Input First line of the input contains the number of test cases T. It is followed by T lines. Each line has a single string M.
Output For each test case, output a single number, the number of valid substrings.
Constraints |M| ≤ 10^6 M contains only lower case latin latters, that is characters a to z.
Read the editorial here.
SAMPLE INPUT 4 abcd azazaz abbzbba flkjdh
SAMPLE OUTPUT 4 21 22 0
Assistant
We need to count the number of substrings (contiguous) of a given string M that contain at least one 'a' or at least one 'z' (or both). The string consists of lowercase letters a-z.
Given constraints |M| <= 10^6, and T test cases. The sum of lengths across test cases could be up to maybe 10^6 or more? The problem statement only says |M| ≤ 10^6 per test case, not total sum. But we need efficient algorithm: O(n) per test case.
The number of total substrings of a string of length n is n*(n+1)/2. We want those substrings that contain at least one 'a' or 'z'. Equivalent to total substrings minus those that contain no 'a' and no 'z' (i.e., only letters from b-y excluding a and z). Actually careful: characters are a-z; "contains the letter a or z" means at least one occurrence of 'a' or at least one occurrence of 'z'. So the complement: substrings that have no 'a' and no 'z' (i.e., all characters from b,c,...,y but not a or z). Yes, because the alphabet includes all lowercase, so complement set = letters except a and z, which are 24 letters (b through y). So we can compute total substrings and subtract count of substrings that consist entirely of characters not in {a,z}.
Thus: answer = total_substrings - number_of_substrings_with_no_a_and_no_z.
We can compute number_of_substrings_with_no_a_and_no_z by considering maximal contiguous blocks of "allowed" characters (i.e., characters other than 'a' and 'z') and for each such block of length L, the number of substrings entirely within that block is L*(L+1)/2. Sum those, then subtract from total.
That's O(n) per test case, easy.
Check sample:
-
"abcd": characters: a,b,c,d. Allowed chars for complement: not a or z: b,c,d. Actually block: after a, we have b,c,d? But it's contiguous, but a is not allowed in complement block; so we need contiguous segments with no a or z. The string: a (invalid for complement), b,c,d (all are not a or z, so complement block of length 3). So substrings with no a/z = 34/2=6. Total substrings = 45/2=10. Answer = 10-6=4. Sample says 4. Good.
-
"azazaz": length 6, total = 21. Let's compute complement: characters that are not a or z? The string is a,z,a,z,a,z. All characters are a or z, so there are no blocks of allowed characters (since complement set excludes a and z). So complement count = 0. Answer = 21. Sample says 21. Good.
-
"abbzbba": length 7, total = 28. The string: a b b z b b a. Identify complement blocks (no a or z): positions: 1:a (not allowed), 2:b (allowed),3:b (allowed),4:z (not),5:b (allowed),6:b (allowed),7:a (not). So blocks: length2 at positions 2-3 => L=2 => 2*3/2=3. length2 at positions5-6 => L=2 =>3. Total complement=6. Answer = 28-6=22. Sample says 22. Good.
-
"flkjdh": no a or z, all letters are from b-y? Actually f,l,k,j,d,h none are a or z. So entire string length 6, complement block length 6 => 6*7/2=21. Total = 21. Answer=21-21=0. Sample says 0. Good.
So algorithm is straightforward.
But wait, constraints: length up to 10^6, T unspecified. Could be many test cases, but total length likely within manageable. We'll implement reading all lines.
Edge cases: empty string? Possibly not, but length >=1? Probably at least 1.
Implement for each test case:
- read string s.
- n = s.length()
- total = n*(n+1)//2
- count_bad = 0
- traverse s, when we find char != 'a' and char != 'z', we count length of consecutive such chars; else when we hit a or z, we finalize the previous run.
Pseudo:
bad = 0 i=0 while i < n: if s[i] != 'a' and s[i] != 'z': j = i while j < n and (s[j] != 'a' and s[j] != 'z'): j++ L = j - i bad += L*(L+1)//2 i = j else: i++
answer = total - bad print answer
But careful: total can be up to ~5e11 for n=1e6 => about 5e11, fits in 64-bit signed (max ~9e18). So use long long in C++ (int64 in Python automatically big). So Python int fine.
That's all.
Now the problem says "Read the editorial here." but no need.
Thus final solution: for each test case, compute as described.
But wait, is that all? Could there be any twist? Let's check: "contains the letter a or z" meaning at least one a or at least one z. Yes.
But maybe there is nuance: The alien language string is said to be valid if it contains the letter a or z. But what about substring? It counts if it contains at least one a or at least one z. Yes.
So algorithm done.
Let's implement in Python:
import sys
def solve(): data = sys.stdin.read().split() t = int(data[0]) out = [] idx = 1 for _ in range(t): s = data[idx] idx += 1 n = len(s) total = n*(n+1)//2 bad = 0 i = 0 while i < n: if s[i] != 'a' and s[i] != 'z': j = i while j < n and s[j] != 'a' and s[j] != 'z': j += 1 L = j - i bad += L*(L+1)//2 i = j else: i += 1 out.append(str(total - bad)) sys.stdout.write("\n".join(out))
if name == "main": solve()
That should pass.
But wait: The problem statement might have larger total length. For T up to maybe 10^5 with small strings? But reading with sys.stdin.read is fine.
Alternatively, we can use two-pointer to accumulate length of contiguous 'bad' chars.
Simplify: iterate and keep a running count of consecutive bad chars:
bad = 0 cur = 0 for ch in s: if ch != 'a' and ch != 'z': cur += 1 else: if cur > 0: bad += cur*(cur+1)//2 cur = 0 After loop, if cur > 0: bad += cur*(cur+1)//2.
But careful: when char is a or z, we reset and add. That works.
But note: For very large n, computing cur*(cur+1)//2 each time cur resets could be okay. But if there are many small resets, it's still O(n). The multiplication of potentially large numbers, but fine.
Potential overflow? Python handles.
Thus solution.
Now I'll produce final answer.
But also note: The problem says "Alice got a message M. It is in an alien language. ... Alice decided to count the number of valid substrings of the message M. Help him to do this." "him"? Not important.
Alright, final answer.
We can also compute directly: total substrings minus sum over blocks of characters not a/z.
Thus, we can implement.
But wait: The problem may be trick: In some problems, they may require use of inclusion-exclusion? But here it's simple complement.
Given sample matches.
Thus answer.
Now produce final code with explanation. ```python
import sys
def solve() -> None: data = sys.stdin.read().split() if not data: return t = int(data[0]) out = [] idx = 1 for _ in range(t): s = data[idx] idx += 1 n = len(s)
total = n * (n + 1) // 2 # all substrings bad = 0 # substrings without 'a' and 'z' cur_len = 0 for ch in s: if ch != 'a' and ch != 'z': cur_len += 1 else: if cur_len: bad += cur_len * (cur_len + 1) // 2 cur_len = 0 # last segment, if any if cur_len: bad += cur_len * (cur_len + 1) // 2 out.append(str(total - bad)) sys.stdout.write("\n".join(out))if name == "main": solve()
-