max-vowels-in-substring.dart (1367B)
1 //Find the largest number of vowels in a string where k 2 //is the greatest window size. To do this I used a set 3 //of all vowels so I could check if a letter was a vowel in 4 //constant time. Then if it was I would check the entire window 5 //to see if it was the largest number of vowels in a given window. 6 //The time complexity of this code is O(n^2) where n is the number 7 //of characters in string s. 8 //Time: 1519ms Beats: 100% 9 //Memory: 148.4MB Beats: 100% 10 //This question is way too difficult for dart because 11 //many solutions that should work do not due to compile time. 12 13 class Solution { 14 int maxVowels(String s, int k) { 15 Set vowels = {}; 16 vowels.add('a'); 17 vowels.add('e'); 18 vowels.add('i'); 19 vowels.add('o'); 20 vowels.add('u'); 21 int highest = 0; 22 int current = 0; 23 int next_vowel = 0; 24 for(int i = 0 ; i < s.length; ++i){ 25 if(vowels.contains(s[i])){ 26 current = 1; 27 for(int x = i + 1; x < i + k && x < s.length ; ++x){ 28 if(vowels.contains(s[x])){ 29 if(next_vowel == 0){ 30 next_vowel = x; 31 } 32 current += 1; 33 } 34 } 35 if(current > highest){ 36 highest = current; 37 } 38 } 39 } 40 return highest; 41 } 42 }