Message on Whatsapp 8879355057 for DSA(OA + Interview) + Fullstack Dev Training + 1-1 Personalized Mentoring to get 10+LPA Job
0 like 0 dislike
2,900 views
String consists of small case letters from 'a' to 'z' ..

Good string is a string which has atleast one vowel & one consonant :)

1<=N<=100000

Expected solutions :

1)O(N^2)

2)O(N) Optimized
in Algorithms and Problems by Expert (107,750 points)
edited by | 2,900 views

2 Answers

0 like 0 dislike
O(N^2)
We may loop through all potential substrings of the supplied string and see if they are good strings in this solution. To determine whether a string is good, we can look for at least one vowel and one consonant in the substring.

O(N2) time complexity

Java source code:

[code]```public static int countGoodSubstrings(String s) {
    int count = 0;
    for (int i = 0; i < s.length(); i++) {
        boolean hasVowel = false, hasConsonant = false;
        for (int j = i; j < s.length(); j++) {
            if (isVowel(s.charAt(j))) {
                hasVowel = true;
            } else {
                hasConsonant = true;
            }
            if (hasVowel && hasConsonant) {
                count++;
            }
        }
    }
    return count;
}

public static boolean isVowel(char c) {
    return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
}```
[/code]
by Expert (650 points)
0 like 0 dislike
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll ; 

int main() {
    
    
    string s ; 
    cin>>s ; 
    ll consonants = -1; 
    ll vowels = -1;
    
    
    ll n = s.size();
    
    
    ll i = 0 ; 
    ll ans = 0 ; 
    while(i<n)
    {
        
        if(s[i]=='a' || s[i]=='e' || s[i]=='i' || s[i]=='o' || s[i]=='u'){
            if(consonants>=0){
           ans+= (consonants+1) ; }
        }
        else
        {
            if(vowels>=0){
          ans+= (vowels+1) ; }
        }
        
        
        
        if(s[i]=='a' || s[i]=='e' || s[i]=='i' || s[i]=='o' || s[i]=='u'){
            vowels = i ; 
        }
        else
        {
            consonants = i ; 
        }
        
        i++;
    }
    cout<<ans; 
    return 0;
    
}
by Expert (107,750 points)