PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: iceknight1093
Tester: raysh07
Editorialist: iceknight1093
DIFFICULTY:
Cakewalk
PREREQUISITES:
None
PROBLEM:
Given a string S representing a word, decide if the word is hard to pronounce.
A word is hard to pronounce if it contains a substring of length \ge 4 such that all the letters are consonants, i.e. letters other than {a, e, i, o, u}.
EXPLANATION:
The simplest way to solve this problem is to simply brute-force check all contiguous sequences.
Fix two indices i and j such that 1 \le i \le j \le N, and j-i+1 \ge 4. This corresponds to a segment of characters having length \ge 4, namely from index i to index j in the string.
Then, check all of the characters S_i, S_{i+1}, \ldots, S_j. If all of them are consonants, then we have \ge 4 consecutive consonants so the string is hard to pronounce.
If the above check works for at least one pair (i, j), the answer is Yes. Otherwise, the answer is No.
This has a complexity of either \mathcal{O}(N^2) or \mathcal{O}(N^3) depending on implementation. Either one is fast enough for the given constraints.
For a faster solution, note that if a string has \ge 4 characters in a row that are consonants, then certainly it must have exactly 4 consonants in a row too.
So, it suffices to just check for all possibilities of 4 characters in a row, i.e. check if all of (S_i, S_{i+1}, S_{i+2}, S_{i+3}) are consonants for some index i.
If this is true for some i, the answer is Yes, otherwise it’s No.
This brings the complexity down to \mathcal{O}(N).
TIME COMPLEXITY:
\mathcal{O}(N) per testcase.
CODE:
Editorialist's code (PyPy3)
for _ in range(int(input())):
n = int(input())
s = input()
vowels = 'aeiou'
ans = 'No'
for i in range(n):
if i+3 >= n: break
ct = 0
for j in range(4): ct += s[i+j] not in vowels
if ct == 4: ans = 'Yes'
print(ans)