mediumStringsPattern: Sliding Window
Vowel-Restricted Identical Border Substring Solution
Problem Statement
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.
Examples
Example 1:
Input:s = "abacaba", k = 2
Output:5
Explanation: The substring "bacab" starts and ends with 'b'. It contains exactly 2 vowels ('a' and 'a'), which is at most k. Its length is 5. Any longer substring with identical ends, like "abacaba" (starts/ends with 'a'), contains 4 vowels, which exceeds k.
Example 2:
Input:s = "rebecca", k = 1
Output:2
Explanation: The substring "cc" starts and ends with 'c' and contains 0 vowels, which is less than or equal to 1. The substring "ebe" starts and ends with 'e' but contains 2 vowels, which exceeds k. The maximum valid length is 2.
Constraints
- 1 <= s.length <= 10^5
- 0 <= k <= s.length
- s consists only of lowercase English letters.
Time: O(n) Space: O(n)
Precompute the prefix sum of vowels to allow O(1) vowel counting. Group all occurrences of each character by index and use a two-pointer approach within each group to find the widest valid window, achieving O(n) total time.
Run, Test & Submit Code
Ready to practice this challenge? Launch our interactive compilation environment with compiler validation.
Solve on Interactive WorkspaceTested Solutions
No solution code is currently loaded.
Complete this code in the workspace editor.