牛客 重新排列 尺取法

排列 尺取法"/>

牛客 重新排列 尺取法

题目描述

牛牛有个很喜欢的字符串”puleyaknoi“。

牛牛有T个很长很长的字符串，他很喜欢把字符串中的子串（连续的某段）打乱，并且按照自己的喜好重新排列。

如果牛牛能把一段重新排列出他喜欢的字符串，他就会把这个子串称作：喜欢的子串。

牛牛是个懒人，他不喜欢对太长的子串进行重排，那样他会觉着眼镜很累。

你能帮他求出对于每个字符串，最短的喜欢的子串的长度是多少吗？

如果没有，请输出-1。

输入描述:

第一行一个表示数据组数接下来行每行一个字符串（保证字符串只含小写字母）

输出描述:

共T行每行一个答案

示例1

输入

2
sxpuleyaaknoip
konijiwa

输出

11
-1

说明

sxpuleyaaknoip中puleyaaknoi可以重排成puleyaknoia，其中包含有puleyaknoi。
konijiwa不能重新排列出puleyaknoi，所以是-1

备注:

字符串长度不超过1e5

参考链接罗永军老师的博客尺取法

尺取法（双指针）

题目分析：刚刚开始看到这个题目的时候，感觉很不好做，唯一想到的方法就是暴力，但是很显然暴力一定会超时，一看题解发现是个尺取法的经典例题，无奈这种题目做的比较少，看懂代码也花了一定的时间，也参考了博客理解尺取法的概念与用法。具体题目分析见代码

#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() //判断函数，判断元素的个数是否满足题目要求
{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']++; //记录目标子串每个元素的个数getchar();           //获取回车，防止干扰后序字符串的输入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) //寻找目标子串，r一直右移直到当前区间[l,r]内出现目标子串a[c[r++] - 'a']++;if (solve()) //一旦出现目标子串就记录一下此时的最小区间ans = min(ans, r - l);a[c[l] - 'a']--; //l不断的右移，每次都除去一个最左边的元素，目标就是找到最小区间}if (ans == inf) //没有找到puts("-1");elseprintf("%d\n", ans);}return 0;
}