Problem Statement

Almost Matching Substrings Problem Description Suppose you are designing a brand-new programming language and want to add a novel string-comparison feature. Ordinary languages can tell you whether two strings match exactly, but yours should also detect when two strings are almost matching : that is, they have the same length, and every character lines up the same in both except for exactly one position. For instance, "cat" and "bat" are almost matching, while "cat" and "dog" are not. To try this feature out efficiently, you decide to test it against all substrings drawn from one fixed string rather than pairs of separate strings. Given a string s and an integer k , count the pairs of substrings of s that are almost matching and whose single differing position is exactly the k th character (0-based) of each substring. Both substrings in a pair must be long enough to actually have a k th character. Note also that a substring is identified by its start and end indices rather than just its