I was approached by a recruiter. First, I had a 30-minute call with the recruiter where we discussed my experience. At the end of the call, I was asked some Big O-notation questions.

The next step was an online interview involving solving a coding question. This question required knowledge of trie structures, which was beyond the average level for a new graduate. We discussed a solution, but I didn't have time to complete the code.

Given two strings s and t, find the number of ways you can choose a non-empty substring of s and replace a single character with a different character such that the resulting substring is a substring of t. In other words, find the number of substrings in s that differ from some substring in t by exactly one character.