Solução Informática Iniciante - Semana 53 - Problema 1

Solução por Lúcio Cardoso

Primeiramente, vamos encontrar a posição mais à esquerda em S que contém a letra "h", denotando-a por pos_h. Após isso, encontraremos a letra "e" mais à esquerda e à direita de pos_e. Repetimos o processo de maneira análoga para as próximas letras da palavra "hello", encontrando pos_{l1}, pos_{l2} e pos_o. Se todas essas posições existirem, encontramos a palavra "hello" e logo a resposta é "SIM". Caso contrário, a resposta será "NAO".

Complexidade: O(n).

Segue o código para melhor entendimento:


// Noic - Iniciante - Semana 53 - Problema 1
// O(n)
#include <bits/stdc++.h>
using namespace std;
int main(void)
{
string s;
int pos_h, pos_e, pos_l1, pos_l2, pos_o;
pos_h = pos_e = pos_l1 = pos_l2 = pos_o = -1; // com -1 indicamos que a posição não foi encontrada ainda
cin >> s;
for (int i = 0; i < s.size(); i++)
{
if (s[i] == 'h') pos_h = i;
else if (s[i] == 'e' && pos_h != -1) pos_e = i;
else if (s[i] == 'l' && pos_e != -1 && pos_l1 == -1) pos_l1 = i;
else if (s[i] == 'l' && pos_l1 != -1) pos_l2 = i;
else if (s[i] == 'o' && pos_l2 != -1) pos_o = i;
}
if (pos_h != -1 && pos_e != -1 && pos_l1 != -1 && pos_l2 != -1 && pos_o != -1) printf("SIM\n");
else printf("NAO\n");
}