HAPPYSTR - Editorial

editorial
,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: Mradul Bhatnagar
Tester: Takuki Kurokawa
Editorialist: Nishank Suresh

DIFFICULTY:

TBD

PREREQUISITES:

None

PROBLEM:

Chef is happy with a string if it contains a substring of length strictly larger than 2 consisting of only vowels. Is Chef happy with string S?

EXPLANATION:

If there exists a substring of length more than 2 consisting of only vowels, then there definitely exists a substring of length 3 containing only vowels: for example, just take the first 3 characters of this substring.

So, all we need to do is determine whether some substring of length 3 consists of only vowels. There are N-2 such substrings, so we can simply use a loop and check all of them.

That is, run a loop of i from 1 to N-2. For each i, check if all 3 of \{S_i, S_{i+1}, S_{i+2}\} are vowels. If this is true for any i, the answer is “Happy”. Otherwise, the answer is “Sad”.

TIME COMPLEXITY

\mathcal{O}(N) per test case.

CODE:

Editorialist's code (Python) 
def count(s):
    return sum('aeiou'.count(x) for x in s) == 3
for _ in range(int(input())):
    s = input()
    print('Happy' if sum(count(s[i:i+3]) for i in range(len(s)-2)) > 0 else 'Sad')