Vowel-Restricted Identical Border Substring — Problem Statement & Solution Guide

StringsMediumSliding Window

TimeO(n)

SpaceO(n)

Quick Answer & Algorithm Key Takeaway

Master coding challenges related to Strings and solve the Vowel-Restricted Identical Border Substring problem optimally.

TopicStrings

PatternSliding Window

TimeO(n)

SpaceO(n)

Problem Description

Given a string s consisting of lowercase English letters and an integer k, find the length of the longest substring that starts and ends with the same character, and contains at most k vowels ('a', 'e', 'i', 'o', 'u'). If no such substring exists, return 0.

DSA Pattern Breakdown

"Vowel-Restricted Identical Border Substring"

medium

WHY DOES IT MATTER?

The pattern blends prefix‑sum queries with a character‑wise two‑pointer scan, a common technique for problems that impose both a value constraint (vowel count) and a positional constraint (identical borders). Mastering this pattern enables efficient handling of many substring‑selection challenges where naive enumeration would be prohibitive.

OPTIMIZATION CHALLENGE

The key insight is that vowel count over any interval can be answered in O(1) using a prefix sum, turning a potentially O(length) inner loop into a constant‑time check. Coupled with the monotonic two‑pointer walk on each character’s index list, each index is processed only twice, collapsing the quadratic explosion to linear time.

REAL-WORLD CONNECTION

Think of a distributed log where each entry has a tag (the character) and a cost metric (vowel count). Finding the longest contiguous segment that starts and ends with the same tag while staying under a budget mirrors load‑balancing or rate‑limiting decisions in micro‑service pipelines.

When coding, first build the vowel prefix array, then group indices by character using an array of vectors. Iterate over each vector with left/right pointers; always compute vowel count via the prefix array before deciding to move pointers. This keeps the code clean and avoids off‑by‑one errors.

COMPLEXITY AT A GLANCE

⏱ Time:O(n)

💾 Space:O(n)

Core Theory — Why This Approach?

The problem asks for the maximum length of a substring whose first and last characters are identical and whose vowel count does not exceed a given threshold k. A naïve solution would enumerate every possible pair of equal‑character positions, extract the substring, count its vowels, and keep the best length. This brute‑force method runs in O(n²) time because there are O(n²) pairs in the worst case, which quickly becomes infeasible for strings of length up to 10⁵ or more.

The optimal paradigm combines prefix‑sum vowel counting with a two‑pointer (sliding‑window) technique applied separately to each character class. By pre‑computing a cumulative vowel count array, we can query the number of vowels in any interval [l, r] in O(1) time: vowels(l, r) = pref[r] – pref[l‑1]. For each of the 26 lowercase letters we collect the indices where that letter appears. On this ordered list we slide a left pointer while expanding a right pointer, maintaining the vowel constraint using the prefix sums. Because each index is visited at most twice across all characters, the total work stays linear.

This approach leverages the monotonicity of the vowel count: as the right pointer moves forward the vowel count never decreases, allowing us to advance the left pointer only when the constraint is violated. The result is an O(n) time algorithm with O(n) auxiliary space for the prefix array and the index buckets, which is optimal for the input size.

Interview Questions on This Problem

Q1How would you modify the solution if the substring must contain exactly k vowels instead of at most k?

Replace the ‘<= k’ check with ‘== k’. While sliding the right pointer, keep expanding until the vowel count reaches k, then record the length. When the count exceeds k, move the left pointer until it drops back to k. The rest of the algorithm (prefix sums and per‑character buckets) stays unchanged, still O(n).

Q2Can the algorithm be extended to handle Unicode strings with an arbitrary set of vowel characters?

Yes. Build a hash set of vowel code points, compute the prefix sum using that set, and bucket indices by character (which may now be a Unicode code point). The sliding window logic remains identical; only the space for buckets grows with the number of distinct characters, still O(n) overall.

Q3What is the time‑space trade‑off if you are allowed only O(1) extra space besides the input string?

You can avoid storing the per‑character index lists by scanning the string twice: first pass to compute the prefix vowel array, second pass to use a sliding window that tracks the first occurrence of each character within the current window via a fixed‑size array of size 26. This yields O(n) time and O(1) extra space (ignoring the input and prefix array, which can be computed on the fly with two pointers).

Examples

Example 1

Input

s = 'aba', k = 1

Output

Explanation: Step-by-step: with input s = 'aba' and k = 1, we find the longest substring that starts and ends with the same character and contains at most k vowels. The substring 'ab' does not meet the criteria because it starts with 'a' and ends with 'b'. However, the substring 'ba' also does not meet the criteria for the same reason. The substring 'aba' meets the criteria because it starts and ends with 'a' and contains 1 vowel, which is within the limit of k = 1. Therefore, the length of the longest substring that meets the criteria is 2, which is the length of 'aa' is not present but 'aba' is present and 'a' is the common character.

Example 2

Input

s = 'cc', k = 0

Output

Explanation: Step-by-step: with input s = 'cc' and k = 0, we find the longest substring that starts and ends with the same character and contains at most k vowels. The substring 'cc' meets the criteria because it starts and ends with 'c' and contains 0 vowels, which is within the limit of k = 0. Therefore, the length of the longest substring that meets the criteria is 2.

Constraints

1 <= s.length <= 10^5
0 <= k <= s.length
s consists only of lowercase English letters.

Optimal Approach & Strategy

Use a prefix‑sum array for vowel counts and a per‑character two‑pointer scan on the list of indices, achieving O(n) time.

Brute Force Approach

Enumerate every pair of equal characters, extract the substring, count its vowels, and keep the maximum length; this is O(n²) time.

Code Solutions

Language:

JavaScript Solution

Time: O(n)

/**
 * @param {string} s
 * @param {number} k
 * @return {number}
 */
var longestVowelRestrictedSubstring = function(s, k) {
    const n = s.length;
    if (n === 0) return 0;
    
    const isVowel = (c) => 'aeiou'.includes(c);
    
    let maxLen = 0;
    
    for (let i = 0; i < n; i++) {
        for (let j = i; j < n; j++) {
            if (s[i] !== s[j]) continue;
            
            let vowels = 0;
            let valid = true;
            for (let m = i; m <= j; m++) {
                if (isVowel(s[m])) {
                    vowels++;
                    if (vowels > k) {
                        valid = false;
                        break;
                    }
                }
            }
            
            if (valid) {
                maxLen = Math.max(maxLen, j - i + 1);
            }
        }
    }
    
    return maxLen;
};

class Solution {
public:
    int longestVowelRestrictedSubstring(string s, int k) {
        int n = s.size();
        if (n == 0) return 0;
        
        auto isVowel = [](char c) {
            return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
        };

        int maxLen = 0;
        
        for (int i = 0; i < n; ++i) {
            for (int j = i; j < n; ++j) {
                if (s[i] != s[j]) continue;
                
                int vowels = 0;
                bool valid = true;
                for (int m = i; m <= j; ++m) {
                    if (isVowel(s[m])) {
                        vowels++;
                        if (vowels > k) {
                            valid = false;
                            break;
                        }
                    }
                }
                
                if (valid) {
                    maxLen = max(maxLen, j - i + 1);
                }
            }
        }
        
        return maxLen;
    }
};

class Solution {
    public int longestVowelRestrictedSubstring(String s, int k) {
        int n = s.length();
        if (n == 0) return 0;
        
        int maxLen = 0;
        
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                if (s.charAt(i) != s.charAt(j)) continue;
                
                int vowels = 0;
                boolean valid = true;
                for (int m = i; m <= j; m++) {
                    char c = s.charAt(m);
                    if (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u') {
                        vowels++;
                        if (vowels > k) {
                            valid = false;
                            break;
                        }
                    }
                }
                
                if (valid) {
                    maxLen = Math.max(maxLen, j - i + 1);
                }
            }
        }
        
        return maxLen;
    }
}

class Solution:
    def longestVowelRestrictedSubstring(self, s: str, k: int) -> int:
        n = len(s)
        if n == 0:
            return 0
        
        vowels = set('aeiou')
        max_len = 0
        
        for i in range(n):
            for j in range(i, n):
                if s[i] != s[j]:
                    continue
                
                vowel_count = 0
                valid = True
                for m in range(i, j + 1):
                    if s[m] in vowels:
                        vowel_count += 1
                        if vowel_count > k:
                            valid = False
                            break
                
                if valid:
                    max_len = max(max_len, j - i + 1)
        
        return max_len

/**
 * @param {string} s
 * @param {number} k
 * @return {number}
 */
var longestVowelRestrictedSubstring = function(s, k) {
    const n = s.length;
    if (n === 0) return 0;
    
    const isVowel = (c) => 'aeiou'.includes(c);
    
    let maxLen = 0;
    
    for (let i = 0; i < n; i++) {
        for (let j = i; j < n; j++) {
            if (s[i] !== s[j]) continue;
            
            let vowels = 0;
            let valid = true;
            for (let m = i; m <= j; m++) {
                if (isVowel(s[m])) {
                    vowels++;
                    if (vowels > k) {
                        valid = false;
                        break;
                    }
                }
            }
            
            if (valid) {
                maxLen = Math.max(maxLen, j - i + 1);
            }
        }
    }
    
    return maxLen;
};

Asked in Top Tech Interviews

SwiggyMicrosoft

Solve in Interative Editor

Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.