Dada una cadena s que consiste solo en letras minúsculas en inglés de longitud NORTE, la tarea es encontrar el número de subcadenas para que cada subcadena contenga al menos 1 vocal y 1 consonante.
Ejemplos:
Aporte: S = «feliz cumpleaños»
Salida: 3
Explicación: S se puede dividir como «ha», «ppybi», «cumpleaños»Aporte: S = «geeksforgeeks»
Salida: 5
Explicación: S se puede dividir como “edad“, “eek“, “OFS“, “rge», «eks»
Acercarse: Siga la siguiente idea para resolver el problema:
La idea es tomar el enfoque codicioso, atravesar la cadena y cada vez que encontramos 1 vocal y 1 consonante, aumentar el conteo en 1 y restablecer el número de vocales y consonantes a 0.
Siga los pasos a continuación para resolver el problema:
- Inicializar variable respuesta = 0haveVowels = false (la cadena actual tiene vocales o no), haveConsonants = false (la cadena actual tiene consonantes o no)
- Repasa la cadena con cada carácter.
- Si el carácter actual son vocales, haga haveVowels = true; de lo contrario, haveConsonants = true
- Cuando ambos son verdaderos, considere que el subsegmento actual es una subcadena válida, incremente respuesta por medio de 1hacer haveVowels = false y haveConsonants = false.
A continuación encontrará la implementación del enfoque anterior.
Python3
|
Complejidad del tiempo: A)
cuarto auxiliar: O(1)