How can I optimize this function?

Currently just looking for a way to make this code faster.

This function currently takes in a string, s, and an int, k, and returns the substring of s length k with the most vowels.

Example:

s = caberqiitefg
k = 5

Output:
erqii

erqii is a substring of length 5 with the most vowels in s.

Returns “Not found!” if there are no vowels in the string.

function findSubstring(s, k)
    local sub = string.sub
    local gsub = string.gsub
    local vowels = "[aeiou]"
    local empty = ""
    if #s - #gsub(s, vowels, empty) == 0 then
        return "Not found!"
    end
    local mostVowels = nil
    local vowelnum = 0
    for i = 1,#s do
        local curr = sub(s,i,k+i-1)
        local currnum = #curr
        if currnum == k then
            local nvow = gsub(curr, vowels, empty)
            if mostVowels == nil or (currnum-#nvow > vowelnum) then
               mostVowels = curr
                vowelnum = #mostVowels - #gsub(mostVowels, vowels, empty)
            end
        end
    end
    return mostVowels
end

(Keep in mind I didn’t benchmark either of these, so I’m not sure how much of a difference they’ll make.)

gsub’s second return is the number of vowels it replaced, so you might want to use that instead of getting the length of what it returns and subtracting it. Also, instead of getting the length of the substring each time, just make sure the substring will always be at least k length by setting the end of the iterator to be sooner. Example of both of those changes:

local _, numberOfVowels = gsub(s, vowels, empty)
if numberOfVowels == 0 then
    return "Not found!"
end
local mostVowels = nil
local vowelnum = 0
for i = 1, #s - k + 1 do
    local curr = sub(s, i, k + i - 1)
    local _, nvow = gsub(curr, vowels, empty)
    if mostVowels == nil or (nvow > vowelnum) then
        mostVowels = curr
        vowelnum = #mostVowels - #gsub(mostVowels, vowels, empty)
    end
end
5 Likes

Aha, thank you.

This is slightly faster than what I was doing.

Completely forgot about gsub’s second return. Makes a big difference lol

1 Like