I have a string of lowercase English letters and an integer of the substring length. I have to find the substring of that length that contains the most vowels.

Example:

s = 'azerdii'

k = 5

The possible 5 character substrings are:

1. 'azerd' No. of vowels = 2
2. 'zerdi' No. of vowels = 2
3. 'erdii' No. of vowels = 3

So the answer should be 'erdii'

Here is my code:

def findSubstring(s, k):
    i = 0
    lst = []
    count = 0
    tempL = []
    
    while(i != len(s)):
        a = i k
        temp = s[i:a]
        lst.append(temp)
        if a != len(s):
            i =1
        else:
            break
    
    for word in lst:
        for alphabet in word:
            if alphabet in 'aeiou':
                count  = 1
        tempL.append(count)
    print(lst)
    print(tempL)
    return 

s = input()

k = int(input().strip())

print(findSubstring(s, k))

I'm getting 

['azerd', 'zerdi', 'erdii']
[2, 4, 7]

But the count should be

[2, 2, 3]

Please forgive any stupid errors I may have. I will certainly appreciate any help.

CodePudding user response：

Try the following:

def find_substr(s, k):
    substrings = [s[i:i k] for i in range(len(s) - k   1)] # list of substrings
    # vowels = [sum(c in 'aeiou' for c in s) for s in substrings]
    # print(vowels) # [2, 2, 3]
    return max(substrings, key=lambda s: sum(c in 'aeiou' for c in s))

print(find_substr('azerdii', 5)) # 'erdii'

If you un-comment the lines that are commented out, you will see the number of vowels is correctly computed as [2, 2, 3].

Here, sum(c in 'aeiou' for c in s) gets the number of vowels in a string s, which is equivalent to

count = 0
for alphabet in word:
    if alphabet in 'aeiou':
        count  = 1

which in turn is the same as your code, except the line count = 0. After processing each word, you need to reset count. So try adding count = 0 in your code.

CodePudding user response：

You need to reset the count=0 at line number 17.

Try this code

def findSubstring(s, k):
    i = 0
    lst = []
    count = 0
    tempL = []
    
    while(i != len(s)):
        a = i k
        temp = s[i:a]
        lst.append(temp)
        if a != len(s):
            i =1
        else:
            break
    
    for word in lst:
        count = 0
        for alphabet in word:
            if alphabet in 'aeiou':
                count  = 1
        tempL.append(count)
    print(lst)
    print(tempL)
    return 

s = 'azerdii'
k = 5
print(findSubstring(s, k))

CodePudding user response：

You could use a sliding window approach, for an optimal time complexity single-pass solution:

def find_substring_length_k_most_vowels(s: str, k: int) -> str:
    '''Returns any substring of length k that has the max number of vowels.'''
    vowels = set('aeiou')
    max_vowel_count = curr_vowel_count = 0
    max_window_start, max_window_end = 0, -1
    window_start = 0
    for window_end, ch in enumerate(s):
        if ch in vowels:
            curr_vowel_count  = 1
        if window_end - window_start   1 == k:
            if curr_vowel_count > max_vowel_count:
                max_vowel_count = curr_vowel_count
                max_window_start, max_window_end = window_start, window_end
            curr_vowel_count -= 1 if s[window_start] in vowels else 0
            window_start  = 1
    return s[max_window_start:max_window_end   1]


def main() -> None:
    s = 'azerdii'
    k = 5
    print(find_substring_length_k_most_vowels(s, k))


if __name__ == '__main__':
    main()

Output:

erdii