Problem 246699 · hard · Phase 02 Linear Data Structures

One Trim of the Film Reel

strings · counting · equivalence · linear scan

A film reel is a string reel of lowercase letters, one letter per frame (the letter says which scene the frame shows). An editor makes exactly one trim: she removes a block of exactly k consecutive frames and splices the two ends together. Different trims can leave identical reels. Write distinct_trims(reel, k) that returns how many different reels can result.

Examples

Input:  reel = "banana", k = 1
Output: 6
Explanation: anana, bnana, baana, banna, banaa, banan are all different.

Input:  reel = "xyzxya", k = 3
Output: 2
Explanation: cutting at positions 0, 1 or 2 leaves "xya"; cutting at 3 leaves "xyz".

Input:  reel = "reelreel", k = 4
Output: 1

Constraints

  • 1 <= k <= len(reel) <= 2 * 10**5
  • If k == len(reel) the only result is the empty reel, so the answer is 1.

Goals

  • Work out exactly when two different cuts leave the same text
  • Turn a set-of-strings question into a single comparison per position
  • Avoid building quadratic numbers of characters
Starting Python…