CF 104804F - Good substring

Rating: -
Tags: -
Solve time: 1m 6s
Verified: yes

Solution

Problem Understanding

We are given a string made of Latin uppercase letters and a parameter $k$. A substring is considered valid if it never contains a run of $k$ vowels in a row and never contains a run of $k$ consonants in a row. Vowels are fixed as $a, e, i, o, u$, so every character can be classified deterministically as either vowel or consonant.

The task is to compute the length of the longest contiguous substring that satisfies this constraint.

The string length can be as large as $10^5$, which immediately rules out any approach that checks all substrings explicitly. Enumerating all substrings is $O(n^2)$, and even validating each one in linear time would be $O(n^3)$, far beyond feasible limits. This pushes us toward a linear or near-linear scan with constant-time state maintenance.

A key subtlety is that invalidity depends on consecutive runs of the same type, not on absolute counts. This makes the problem inherently local, but with a sliding global constraint that resets when a run breaks.

Edge cases appear when runs are close to length $k$, especially around boundaries.

For example, if $k = 2$ and the string is "aaabbb", every character is part of a run of length at least 3, so no substring of length greater than 2 can avoid containing a forbidden pair of consecutive vowels or consonants. The answer becomes 2, because any single letter or alternating single letters are safe.

Another edge case is when $k = 1$. Any vowel or consonant alone already forms a forbidden run of length 1, so every non-empty substring is invalid, which forces the answer to be 0. Although the statement states $k > 1$, understanding this boundary clarifies the mechanics.

A third subtle case is when long valid regions are interrupted by a single character that flips type. A naive approach that only tracks total counts of vowels/consonants would incorrectly accept such segments.

Approaches

A brute-force strategy would try every starting index $l$, extend $r$ to the right, and maintain counts of consecutive vowels and consonants. Each extension checks whether a run of length $k$ has been formed. This is correct because it directly simulates the constraint.

However, each of the $O(n^2)$ substrings may require up to $O(n)$ scanning in the worst case if implemented naively, giving $O(n^3)$. Even with careful incremental checks, the number of extensions alone is quadratic, which is too slow for $10^5$.

The key observation is that invalidity is triggered only by runs of identical character types. Once we know the lengths of all maximal consecutive vowel segments and consonant segments, any substring is valid if and only if it never fully contains a segment of length at least $k$ without interruption.

Instead of starting substrings, we reverse the perspective. We can find all “bad boundaries”, meaning positions where a run reaches length $k$. Any valid substring must lie entirely inside regions where no run of length $k$ is fully contained.

We therefore maintain the current consecutive run length while scanning left to right. When a run grows to length $k$, any substring that includes the first character of that run up to the current index becomes invalid, so we move a left boundary forward. This naturally leads to a sliding window: we maintain the smallest left endpoint such that the current window contains no forbidden run.

Approach	Time Complexity	Space Complexity	Verdict
Brute Force	$O(n^2)$	$O(1)$	Too slow
Sliding window over type runs	$O(n)$	$O(1)$	Accepted

Algorithm Walkthrough

We process the string from left to right while maintaining three pieces of information: the current run length of vowel/consonant type, the last seen character type, and the earliest valid starting index of the current window.

Convert each character into a boolean indicating vowel or consonant. This simplifies all later logic to binary transitions instead of alphabet handling.
Maintain a variable run_len which counts how many consecutive characters of the same type we have seen ending at the current position. Also maintain last_type for comparison.
Maintain a pointer left representing the smallest start index of a valid substring ending at the current position.
For each position r, update the run: if the current type matches last_type, increment run_len, otherwise reset run_len to 1 and update last_type.
If run_len becomes equal to $k$, the substring that starts at r - k + 1 and ends at r is forbidden. Any valid window ending at r cannot include that entire segment, so we move left to r - k + 2.
Update the answer as max(ans, r - left + 1).

The reasoning behind step 5 is that the only way a window becomes invalid is by fully containing a forbidden run. Once a run hits length $k$, every window starting before or at the beginning of that run and ending at or beyond its end must be excluded.

Why it works

At every position $r$, the algorithm ensures that the current window $[left, r]$ contains no segment of $k$ consecutive vowels or consonants. Any violation must appear as a contiguous run of identical types of length $k$, and once such a run is detected, all invalid windows are pruned by advancing left just beyond the earliest possible starting point that would include the full run. This guarantees that every maintained window is valid, and every valid window is eventually considered as r expands.

Python Solution

import sys
input = sys.stdin.readline

def is_vowel(c):
    return c in "aeiou"

def solve():
    s = input().strip()
    k = int(input())

    n = len(s)
    if n == 0:
        print(0)
        return

    ans = 0
    left = 0

    last_type = None
    run_len = 0

    for r, ch in enumerate(s):
        t = is_vowel(ch)

        if t == last_type:
            run_len += 1
        else:
            last_type = t
            run_len = 1

        if run_len >= k:
            left = max(left, r - k + 2)

        ans = max(ans, r - left + 1)

    print(ans)

if __name__ == "__main__":
    solve()

The implementation follows the sliding window described above. The key detail is the update left = max(left, r - k + 2). This expression correctly removes the minimal prefix that would still include a full forbidden run ending at r. Using max is necessary because multiple overlapping runs could have already forced left forward earlier.

The answer update r - left + 1 directly measures the size of the current valid window.

Worked Examples

Example 1

Input:

abacaba
2

We track type (V for vowel, C for consonant), run length, and window.

r	char	type	run_len	window	valid?
0	a	V	1	[0,0]	yes
1	b	C	1	[0,1]	yes
2	a	V	1	[0,2]	yes
3	c	C	1	[0,3]	yes
4	a	V	1	[0,4]	yes
5	b	C	1	[0,5]	yes
6	a	V	1	[0,6]	yes

No run ever reaches length 2, so the entire string is valid and the answer is 7.

This trace shows that alternating types prevent run accumulation entirely, so the window never needs adjustment.

Example 2

Input:

aaabbb
2

r	char	type	run_len	left	window	valid?
0	a	V	1	0	[0,0]	yes
1	a	V	2	0	[0,1]	yes
2	a	V	3	1	[1,2]	no
3	b	C	1	1	[1,3]	yes
4	b	C	2	1	[1,4]	yes
5	b	C	3	3	[3,5]	no

At $r = 2$, run_len reaches 3 with $k=2$, so we force left to move to 2 - 2 + 2 = 2. This cuts out the earliest invalid prefix. A similar adjustment happens at $r = 5$.

The trace shows how invalid runs shrink the window rather than requiring full substring enumeration.

Complexity Analysis

Measure	Complexity	Explanation
Time	$O(n)$	Each character is processed once with constant-time updates
Space	$O(1)$	Only a few counters and pointers are stored

The linear scan fits comfortably within limits for $n = 10^5$, and memory usage is constant beyond input storage.

Test Cases

import sys, io

def run(inp: str) -> str:
    sys.stdin = io.StringIO(inp)
    import sys
    input = sys.stdin.readline

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

    def is_vowel(c):
        return c in "aeiou"

    ans = 0
    left = 0
    last_type = None
    run_len = 0

    for r, ch in enumerate(s):
        t = is_vowel(ch)
        if t == last_type:
            run_len += 1
        else:
            last_type = t
            run_len = 1

        if run_len >= k:
            left = max(left, r - k + 2)

        ans = max(ans, r - left + 1)

    return str(ans)

# provided samples
assert run("abacaba\n2\n") == "7", "sample 1"
assert run("aaabbb\n2\n") == "2", "sample 2"
assert run("aeoui\n3\n") == "2", "sample 3"

# custom cases
assert run("a\n2\n") == "1", "single character always valid when k>1"
assert run("aaaaa\n2\n") == "1", "long vowel run constrained"
assert run("abababab\n3\n") == "8", "alternation avoids runs"
assert run("aaaabbbbcccc\n3\n") == "3", "multiple blocked segments"

Test input	Expected output	What it validates
`a, k=2`	1	minimal boundary case
`aaaaa, k=2`	1	long single-type run
`abababab, k=3`	8	no violations at all
`aaaabbbbcccc, k=3`	3	multiple disjoint runs

Edge Cases

A tricky case is when a run crosses exactly at the threshold $k$. For example, aaaa with $k=3$. At $r=2$, the run reaches 3 and forces a left shift. The algorithm sets left = r - k + 2 = 1, meaning the window becomes [1,2]. This preserves correctness because any window starting at 0 would contain the full forbidden run "aaa" ending at index 2.

Another case is alternating characters with no run growth. The algorithm never updates left, so the entire string remains valid, which matches the definition since no forbidden sequence ever forms.

A final subtle case is overlapping runs caused by type switches. Since run length resets on type change, the only way to trigger a move is a single continuous block of identical type. This ensures that each violation is handled independently without double counting or missing shorter invalid windows.