Anagram Substring Search

Given two strings \(S\) and \(T\), determine if there exists a substring of \(S\) which is an anagram of \(T\). Formally, find an index \(i\) (0-indexed) such that the substring \(S[i \ldots i+|T|-1]\) satisfies \(\text{freq}(S[i \ldots i+|T|-1]) = \text{freq}(T)\), where \(\text{freq}(X)\) denotes the frequency of characters in string \(X\). If such a substring exists, output its starting index; otherwise, output \(-1\).

inputFormat

The input consists of two lines:

• The first line contains the string \(S\).
• The second line contains the string \(T\).

outputFormat

Output a single integer to stdout: the starting index of the substring in \(S\) that is an anagram of \(T\), or \(-1\) if no such substring exists.

abcdefg
gfed

3