Length of longest substring with k distinct vowels

For a given string S, write a program based on dynamic programming for finding the length of
the longest substring of S which contains exactly K distinct vowels.

Input: s = “artyebui”, k = 2
Output: 6
Explanation: Longest substring with only 2 vowel is “rtyebu”

Can somebody provide me a DP approach to it?

It’s a two-pointers question, although if you don’t want to do it without two-pointers, using DP only, you have to use N^2 space, N being the length of string., which is not preffered
Or
Take a bool array of size 5(or equal to the number of vowels) for storing which vowel is present in that range, and with two-pointers, iterate through the string, trying to keep the length maximum and limiting no of distinct vowels to K.

2 Likes