Niuke rearrangement rule taking method

Title Description

Niuniu has a favorite string ”puleyaknoi“.

Cattle have T A very long string , He likes to put substrings in strings （ A continuous segment ） Upset , And rearrange it to your liking .

If Niuniu can rearrange a paragraph into a string he likes , He would call this substring ： Favorite substring .

Niuniu is a lazy man , He doesn't like to rearrange too long substrings , Then he will feel tired with his glasses .

You can help him find out for each string , What is the length of the shortest favorite substring ？

without , Please export -1.

Input description :

 The first line represents the number of data groups, and the next line contains a string （ Ensure that the string contains only lowercase letters ）

Output description :

 common T One answer per line 

Example 1

Input

2
sxpuleyaaknoip
konijiwa

Output

11
-1

explain

sxpuleyaaknoip in puleyaaknoi Can be rearranged into puleyaknoia, It includes puleyaknoi.
konijiwa Cannot rearrange puleyaknoi, So it is -1

remarks :

 The string length does not exceed 1e5

Reference link luoyongjun's blog Ruler method

Ruler method （ Double pointer ）

Topic analysis ： When I first saw this topic , It feels very difficult to do , The only way to think about it is violence , But it's clear that violence will definitely go out of time , A look at the problem solution shows that it is a classic example of the rule taking method , But this kind of topic has been done less , It took some time to understand the code , I also refer to the blog to understand the concept and usage of ruler taking method . See code for specific topic analysis

#include <bits/stdc++.h>
using namespace std;
string s = "puleyaknoi";
const int maxn = 1e5 + 10;
const int inf = 0x3f3f3f3f;
int a[maxn], b[maxn];
char c[maxn];
int solve() // Judgment function , Judge whether the number of elements meets the requirements of the topic 
{
    
    for (int i = 0; i < 26; ++i)
        if (a[i] < b[i])
            return false;
    return true;
}
int main()
{
    
    int t;
    scanf("%d", &t);
    for (int i = 0; i < s.size(); ++i)
        b[s[i] - 'a']++; // Record the number of each element of the target substring 
    getchar();           // Get carriage return , Prevent interference with the input of subsequent strings 
    for (int i = 1; i <= t; ++i)
    {
    
        scanf("%s", c);
        int lc = strlen(c);
        int r = 0, ans = inf;
        for (int l = 0; l < lc; ++l)
        {
    
            while (!solve() && r < lc) // Find the target substring ,r Move right until the current interval [l,r] The target substring appears in 
                a[c[r++] - 'a']++;
            if (solve()) // Once the target substring appears, record the minimum interval 
                ans = min(ans, r - l);
            a[c[l] - 'a']--; //l Constantly moving right , Remove one leftmost element each time , The goal is to find the minimum interval 
        }
        if (ans == inf) // Can't find 
            puts("-1");
        else
            printf("%d\n", ans);
    }
    return 0;
}

The Mid Autumn Festival is the national day , A good home meets a prosperous country