Almost Matching Substrings

Problem Statement

Almost Matching Substrings Problem Description A text-processing tool is getting a new comparison feature. Checking whether two strings match is easy; the tool should also tell whether two strings are almost matching : they have the same length and are identical except at exactly one position. For example, "cat" and "bat" are almost matching, but "cat" and "dog" are not. To test the feature efficiently, you use a single string and compare its substrings. Given a string s and an integer k , count the pairs of substrings of s that are almost matching and whose one differing position is their k -th character (0-based). Both substrings must be longer than k , otherwise they would not have a k -th character. Substrings are identified by their indices, so the same text occurring at different places gives different substrings. For example, in "ingratiating" the substring "ing" starting at index 0 is distinct from the one starting at index 9 , and there are also two distinct "ati" substrings.