Substring Pairs With One Typo

Medium

You are given strings first and second. Pick a non-empty substring of first and a substring of **the same length** of second. The pair qualifies if the two differ in exactly one position, like a word and the same word with a single typo. Count the qualifying pairs. Substrings are told apart by position, not by text: identical pieces in different places form different pairs.

Example 1

first='ab', second='bb' → 3

The pairs ("a", "b") count twice, since second has two b's, plus ("ab", "bb"). That makes 3.

Example 2

first='cat', second='cut' → 10

Pairs such as ("a", "c"), ("ca", "cu"), ("cat", "cut") and ("at", "ut") differ in exactly one position; there are 10 such pairs in total.

Example 3

first='aaa', second='aaa' → 0

Constraints

1 ≤ len(first), len(second) ≤ 100
Both strings consist of lowercase English letters

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Hash Table String Dynamic Programming Enumeration

Similar problems

Make Letter Counts Equal Hard Split Into Dictionary Words Medium Next Time From the Same Digits Medium Words Hidden in a Text Medium Word Growth Chain Medium

Input

first='ab', second='bb'

Expected

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