Ctrl K

Even Stretches Without Jumps

Hard
You are given a string text of lowercase English letters and an integer times. Call a non-empty stretch of the string (a run of consecutive characters) **even** if both hold: - every letter that appears in it appears exactly times times; - any two neighbouring letters in it are at most two positions apart in the alphabet: a may stand next to c, but not next to d. Return the number of even stretches in text. Stretches at different positions count separately even if they spell the same string.
Example 1
text="aabbzz", times=2 → 4

"aa", "bb", "aabb" and "zz" qualify. "bbzz" does not: b and z are too far apart in the alphabet.

Example 2
text="abcabc", times=1 → 15

We need stretches where every letter appears exactly once: 6 of length 1, 5 of length 2 and 4 of length 3.

Example 3
text="kkk", times=2 → 2

"kk" qualifies at positions 0–1 and at positions 1–2. The whole string does not: it has three ks.

Constraints
  • 1 ≤ len(text) ≤ 10⁵
  • 1 ≤ times ≤ len(text)
  • text consists of lowercase English letters only
Have you seen this problem in a real interview?
Solved by0
Tried by0
Submissions0
Acceptance—
Topics
Similar problemsWord Blocks in Any Order HardShortest Covering Window HardLongest Clean Stretch HardWindows Covering a Letter Set: Large Input HardA Letter Reaches k Repeats: Large Input Hard
loading Python…
Input
text="aabbzz", times=2
Expected
4

Run checks the first 3 tests in your browser. Submit checks all 94 tests on the server, hidden ones included.