How to optimally solve this?

general
, ,
1

This is a problem of Hackerrank Problem Solving basic certification Link.
Description:
Given a string S of lowercase English letters and an integer of the substring length K, determine the substring of that length that contains the most vowels. Vowels are in the set (a,e,i,o,u). If there is more than one substring with the maximum number of vowels, return the one that starts at the lowest index. If there are no vowels in the input string, return -1.
Constraints:
1<= Stringlength <=2*10^5
1<= K <=String length

Example-
S="caberqiitefg"
K=5

Answer- erqii as it contains 3 vowels

My approach was to basically bruteforce approach, how can I optimise it?

2

When you’re solving problems with fixed length of substring or subarray, you can use a sliding window algorithm. Fix the window of length k, and store the number of vowels for that window. Then keep moving the window, and update the number of vowels in your current window.

  • If s[windowEnd + 1] is a vowel, windowCount++;
  • If s[windowStart] is a vowel, windowCount–;

A simple greater than comparison will give you the substring with lowest index.

Detailed Algorithm

3

Can you explain the question properly? The link just takes me to the dashboard.
What is K? Is it the length of the substring that you must find? Is it the minimum number of vowels your string must have?

[UPD]: If substr length is fixed, then I shall revive my previous comment.

4

try using kadanes algorithm

5

You have to take the test of basic problem solving to get the problem, so I don’t have the direct link.
K is the length of the substring in which we have to check the maximum vowels.
In the example, out of all substrings of length 5, erqii have the maximum vowels i.e. 3

6

In the Example, you gave K=3?

7

Sorry, typo. Fixed

8

Ohk. I will try this.Thank you

1 Like
9

try sliding window
Refer this video for clear explanation.This is a different question but good for learning

10

Does this mean you are cheating or is it a practise question?

11

Obviously its a practise question.

13

function findSubstring(s, k) {

var ar = new Array();

var prev = 0,

    now,

    index;

for (var i = 0; i < s.length - k + 1; ++i) {

    ar[i] = s.substr(i, k)

    now = vowelCount(ar[i], ar[i].length)

    if (now > prev) {

        prev = now

        index = i;

    }

}

return ar[index]

}

function vowelCount(s, k) {

var count = 0,

    i = 0;

while (i < k) {

    if (s[i] == 'a' || s[i] == 'e' || s[i] == 'i' || s[i] == 'o' || s[i] == 'u')

        ++count;

    ++i;

}

return count

}

console.log(findSubstring(‘hhoouiihhidgeeefgfxgdfgdfgdhfdgfegdfegdfgedef’, 10));

This is the solution in javascript. Only the function is written.

14

public static String findSubstring(String s, int k) {
int prev_count=0;
String res = “”, string = “”;

char[] array;

for(int i =0; i<= s.length()-k; i++){
    int count = 0;
    string = s.substring(i,i+k);

    array = string.toCharArray();
    for(char c: array){
        if(isVowel(c)){
            count++;
        }
    }
    if(count > prev_count){
        prev_count = count;
        res = string;
        
    }
            
}
if(prev_count == 0)
         return "Not found!";
    else
        return res;
}

static boolean isVowel(char c){

    if (c == 'a' || c== 'e' || c== 'i' || c== 'o' || c== 'u'){
        return true;
    }
    return false;
}

}

15 
str1 = 'caberqiitefg'
k = 5
j = k
max = 0
max_sub = ""
arr = ["a","e","i","o","u"]
for i in range(len(str1)):
    sub = str1[i:j]
    p= 0
    for m in arr:
        p += sub.count(m)
    if p!= 0 and p>max:
        max = p
        max_sub = sub
    j+=1
print(max_sub)
16

Beautiful !