Yet Another String Matching Problem

Suppose you have two strings s and t, and their length is equal. You may perform the following operation any number of times: choose two different characters c₁ and c₂, and replace every occurence of c₁ in both strings with c₂. Let's denote the distance between strings s and t as the minimum number of operations required to make these strings equal. For example, if s is abcd and t is ddcb, the distance between them is 2 — we may replace every occurence of a with b, so s becomes bbcd, and then we may replace every occurence of b with d, so both strings become ddcd.

You are given two strings S and T. For every substring of S consisting of |T| characters you have to determine the distance between this substring and T.