All Tracks Algorithms String Algorithms Basics of String Manipulation Problem

Can you count?
Tag(s):

Algorithms, String Manipulation

Problem
Editorial
Analytics

You are given a string s consisting of lowercase English letters and/or '_' (underscore).
You have to replace all underscores (if any) with vowels present in the string.

The rule you follow is:
Each underscore can be replaced with any one of the vowel(s) that came before it.

You have to tell the total number of distinct strings we can generate following the above rule.

Input format:
The first line consists of an integer t, denoting the number of test cases.
Each of the next t lines consists of a string s.

Output format:
For each test case, output total number of distinct strings we can generate following the given rule.
Answer for each test case should come in a new line.

Input Constraints:
\(1 \le t \le 4000\)
\(1 \le |s| \le 10^5\); s denotes string length.
Sum of s over all test-cases won't exceed \(10^5.\)
It is guaranteed that there will be atleast one vowel before any '_' (underscore) character in the string.

Note:
It is guaranteed that answer won't go beyond \(5 * 10^{18}\).

SAMPLE INPUT
2
ab_ae_
abc
SAMPLE OUTPUT
2
1
Explanation

Test-case 1: First underscore can be replaced by only one vowel ('a'), while second underscore can be replaced by any one of the two vowels ('a' or 'e').

Distinct strings possible are: 1) abaaea 2) abaaee

So output is 2.

Test-case 2: There are no '_' underscores. So we cannot do any replacement. So given string is the only answer. Output 1.

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, C++17, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, Java 14, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, Python 3.8, R(RScript), Racket, Ruby, Rust, Scala, Swift-4.1, Swift, TypeScript, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

Ubona Technology Pvt Ltd

Challenge Name

Ubona Developer Hiring Challenge

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications

?