First Window With One Typo

Hard

You get strings text and sample. We want to find a place in text where sample appears, possibly with a single typo. A window is a substring of text with the same length as sample. A window fits if it matches sample in every position except at most one. Return the start index of the leftmost window that fits, or -1 if there is none (including when sample is longer than text).

Example 1

text="banana", sample="nab" → 2

"ban" differs from "nab" in two places and "ana" in three, while "nan" (from index 2) differs only in its last letter.

Example 2

text="roses", sample="rise" → 0

The very first window, "rose", differs from "rise" in one letter.

Example 3

text="abc", sample="xy" → -1

Both windows, "ab" and "bc", differ from "xy" in two places, so the answer is -1.

Constraints

1 ≤ len(text), len(sample) ≤ 10⁵
Both strings consist of lowercase English letters

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

String String Matching

Similar problems

Palindrome by Adding Letters in Front Hard Start That Matches the End Hard Strings in a Range Without a Banned Word Hard Suffixes Echoing the Start Hard Pattern With Allowed Swaps Hard

Input

text="banana", sample="nab"

Expected

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