SLDW0104 - Editorial

Problem Link - Special Substring

Problem Statement

Chef gave you a string S of size N which contains only lowercase English letters and asked you to find the length of the longest substring of the string which satisfies the following condition:

  • Each character \beta should appear at most f(\beta) times.

Here f(\beta) denotes the index of the character \beta in the alphabet series. For example f('a') = 1, f('b') = 2 and so on.

Note: A substring of a string is a contiguous subsequence of that string.

Approach

The code uses the sliding window technique to find the longest valid substring. It maintains a frequency map to count occurrences of characters while expanding the right pointer. For each character added, it checks if any character exceeds its allowed frequency based on its position in the alphabet. If so, it adjusts the left pointer to shrink the window until the substring becomes valid again. At each valid state, it updates the maximum length found. This efficiently finds the longest substring meeting the character frequency condition.

Time Complexity

O(N) for each test case, where N is the length of the string.

Space Complexity

O(1) since the frequency map can hold at most 26 characters (lowercase letters).