How should I practice Find the First Almost-Equal Substring?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Google onsite interview problems in FastPrep.

Is Find the First Almost-Equal Substring associated with Google?

FastPrep tags this as a Google onsite interview coding practice problem when the problem catalog has that company and stage context.

Find the First Almost-Equal Substring

Google● HardNEW GRADONSITE INTERVIEW

Learn

Problem statement

You are given lowercase strings s and pattern.

Two equal-length strings are almost equal when changing at most one character in the first can make them identical. Return the smallest starting index of a substring of s that is almost equal to pattern. Return -1 when no such substring exists.

Function

minStartingIndex(s: String, pattern: String) → int

Examples

Example 1

s = "abcdefg"pattern = "bcdffg"return = 1

bcdefg differs from bcdffg in one position.

Example 2

s = "ababbababa"pattern = "bacaba"return = 4

bababa begins at index 4 and differs from the pattern once.

Example 3

s = "abcd"pattern = "dba"return = -1

Every length-three substring differs in more than one position.

Constraints

1 <= pattern.length < s.length <= 100000.
s and pattern contain only lowercase English letters.