Подсчитать подстроки, содержащие все гласные | НАБОР 2
Учитывая строку str, содержащую строчные буквы, задача состоит в том, чтобы подсчитать подстроки, которые содержат все гласные хотя бы один раз, и в подстроках нет согласных (негласных символов).
Примеры:
Input: str = “aeoibsddaaeiouudb”
Output: 4
“aaeiouu”, “aeiouu”, “aeiou” and “aaeiou”Input: str = “aeoisbddiouuaedf”
Output: 1Input: str = “aeouisddaaeeiouua”
Output: 9
Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.
Подход: идея состоит в том, чтобы извлечь все подстроки максимальной длины, содержащие только гласные. Теперь для всех этих подстрок по отдельности нам нужно найти количество подстрок, которые содержат все гласные хотя бы один раз. Это можно сделать, используя технику двух указателей.
Иллюстрация того, как использовать технику двух указателей в этом случае:
If string = “aeoibsddaaeiouudb”
The first step is to extract all maximum length sub-strings that contain only vowels which are:
- aeoi
- aaeiouu
Now, take the first string “aeoi”, it will not be counted because vowel ‘u’ is missing.
Then, take the second substring i.e. “aaeiouu”
Length of the string, n = 7
start = 0
index = 0
count = 0
We will run a loop till all the vowels are present at least once, so we stop at index 5 and start = 0.
Now our string is “aaeiou” and there are n – i substrings that contain vowels at least once and have string “aaeiou” as their prefix.
These substrings are: “aaeiou”, “aaeiouu”
count = count + (n – i) = 7 – 5 = 2
Now, count = 2Then, increment start with 1. If substring between [start, index] i.e (1, 5) still contains vowels at least once then add (n – i).
These substrings are: “aeiou”, “aeiouu”
count = count + (n – i) = 7 – 5 = 2
Now, count = 2Then start = 2, now substring becomes “eiouu”. Then no further count can be added because vowel ‘a’ is missing.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach #include <bits/stdc++.h> using namespace std; // Function that returns true if c is a vowel bool isVowel( char c) { return (c == "a" || c == "e" || c == "i" || c == "o" || c == "u" ); } // Function to return the count of sub-strings // that contain every vowel at least // once and no consonant int countSubstringsUtil(string s) { int count = 0; // Map is used to store count of each vowel map< char , int > mp; int n = s.length(); // Start index is set to 0 initially int start = 0; for ( int i = 0; i < n; i++) { mp[s[i]]++; // If substring till now have all vowels // atleast once increment start index until // there are all vowels present between // (start, i) and add n - i each time while (mp[ "a" ] > 0 && mp[ "e" ] > 0 && mp[ "i" ] > 0 && mp[ "o" ] > 0 && mp[ "u" ] > 0) { count += n - i; mp[s[start]]--; start++; } } return count; } // Function to extract all maximum length // sub-strings in s that contain only vowels // and then calls the countSubstringsUtil() to find // the count of valid sub-strings in that string int countSubstrings(string s) { int count = 0; string temp = "" ; for ( int i = 0; i < s.length(); i++) { // If current character is a vowel then // append it to the temp string if (isVowel(s[i])) { temp += s[i]; } // The sub-string containing all vowels ends here else { // If there was a valid sub-string if (temp.length() > 0) count += countSubstringsUtil(temp); // Reset temp string temp = "" ; } } // For the last valid sub-string if (temp.length() > 0) count += countSubstringsUtil(temp); return count; } // Driver code int main() { string s = "aeouisddaaeeiouua" ; cout << countSubstrings(s) << endl; return 0; } |
Java
// Java implementation of the approach import java.util.*; class GFG { // Function that returns true if c is a vowel static boolean isVowel( char c) { return (c == "a" || c == "e" || c == "i" || c == "o" || c == "u" ); } // Function to return the count of sub-strings // that contain every vowel at least // once and no consonant static int countSubstringsUtil( char []s) { int count = 0 ; // Map is used to store count of each vowel Map<Character, Integer> mp = new HashMap<>(); int n = s.length; // Start index is set to 0 initially int start = 0 ; for ( int i = 0 ; i < n; i++) { if (mp.containsKey(s[i])) { mp.put(s[i], mp.get(s[i]) + 1 ); } else { mp.put(s[i], 1 ); } // If substring till now have all vowels // atleast once increment start index until // there are all vowels present between // (start, i) and add n - i each time while (mp.containsKey( "a" ) && mp.containsKey( "e" ) && mp.containsKey( "i" ) && mp.containsKey( "o" ) && mp.containsKey( "u" ) && mp.get( "a" ) > 0 && mp.get( "e" ) > 0 && mp.get( "i" ) > 0 && mp.get( "o" ) > 0 && mp.get( "u" ) > 0 ) { count += n - i; mp.put(s[start], mp.get(s[start]) - 1 ); start++; } } return count; } // Function to extract all maximum length // sub-strings in s that contain only vowels // and then calls the countSubstringsUtil() to find // the count of valid sub-strings in that string static int countSubstrings(String s) { int count = 0 ; String temp = "" ; for ( int i = 0 ; i < s.length(); i++) { // If current character is a vowel then // append it to the temp string if (isVowel(s.charAt(i))) { temp += s.charAt(i); } // The sub-string containing all vowels ends here else { // If there was a valid sub-string if (temp.length() > 0 ) count += countSubstringsUtil(temp.toCharArray()); // Reset temp string temp = "" ; } } // For the last valid sub-string if (temp.length() > 0 ) count += countSubstringsUtil(temp.toCharArray()); return count; } // Driver code public static void main(String[] args) { String s = "aeouisddaaeeiouua" ; System.out.println(countSubstrings(s)); } } // This code is contributed by Princi Singh |
Python3
# Python3 implementation of the approach # Function that returns true if c is a vowel def isVowel(c) : return (c = = "a" or c = = "e" or c = = "i" or c = = "o" or c = = "u" ); # Function to return the count of sub-strings # that contain every vowel at least # once and no consonant def countSubstringsUtil(s) : count = 0 ; # Map is used to store count of each vowel mp = dict .fromkeys(s, 0 ); n = len (s); # Start index is set to 0 initially start = 0 ; for i in range (n) : mp[s[i]] + = 1 ; # If substring till now have all vowels # atleast once increment start index until # there are all vowels present between # (start, i) and add n - i each time while (mp[ "a" ] > 0 and mp[ "e" ] > 0 and mp[ "i" ] > 0 and mp[ "o" ] > 0 and mp[ "u" ] > 0 ) : count + = n - i; mp[s[start]] - = 1 ; start + = 1 ; return count; # Function to extract all maximum length # sub-strings in s that contain only vowels # and then calls the countSubstringsUtil() to find # the count of valid sub-strings in that string def countSubstrings(s) : count = 0 ; temp = ""; for i in range ( len (s)) : # If current character is a vowel then # append it to the temp string if (isVowel(s[i])) : temp + = s[i]; # The sub-string containing all vowels ends here else : # If there was a valid sub-string if ( len (temp) > 0 ) : count + = countSubstringsUtil(temp); # Reset temp string temp = ""; # For the last valid sub-string if ( len (temp) > 0 ) : count + = countSubstringsUtil(temp); return count; # Driver code if __name__ = = "__main__" : s = "aeouisddaaeeiouua" ; print (countSubstrings(s)); # This code is contributed by AnkitRai01 |
C#
// C# implementation of the approach using System; using System.Collections.Generic; class GFG { // Function that returns true if c is a vowel static bool isVowel( char c) { return (c == "a" || c == "e" || c == "i" || c == "o" || c == "u" ); } // Function to return the count of sub-strings // that contain every vowel at least // once and no consonant static int countSubstringsUtil( char []s) { int count = 0; // Map is used to store count of each vowel Dictionary< char , int > mp = new Dictionary< char , int >(); int n = s.Length; // Start index is set to 0 initially int start = 0; for ( int i = 0; i < n; i++) { if (mp.ContainsKey(s[i])) { mp[s[i]] = mp[s[i]] + 1; } else { mp.Add(s[i], 1); } // If substring till now have all vowels // atleast once increment start index until // there are all vowels present between // (start, i) and add n - i each time while (mp.ContainsKey( "a" ) && mp.ContainsKey( "e" ) && mp.ContainsKey( "i" ) && mp.ContainsKey( "o" ) && mp.ContainsKey( "u" ) && mp[ "a" ] > 0 && mp[ "e" ] > 0 && mp[ "i" ] > 0 && mp[ "o" ] > 0 && mp[ "u" ] > 0) { count += n - i; if (mp.ContainsKey(s[start])) mp[s[start]] = mp[s[start]] - 1; start++; } } return count; } // Function to extract all maximum length // sub-strings in s that contain only vowels // and then calls the countSubstringsUtil() to find // the count of valid sub-strings in that string static int countSubstrings(String s) { int count = 0; String temp = "" ; for ( int i = 0; i < s.Length; i++) { // If current character is a vowel then // append it to the temp string if (isVowel(s[i])) { temp += s[i]; } // The sub-string containing // all vowels ends here else
|