Kirinriki

Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 1012 Accepted Submission(s): 400

Problem Description

We define the distance of two strings A and B with same length n is

disA,B=∑i=0n−1|Ai−Bn−1−i|
The difference between the two characters is defined as the difference in ASCII.
You should find the maximum length of two non-overlapping substrings in given string S, and the distance between them are less then or equal to m.

Input

The first line of the input gives the number of test cases T; T test cases follow.
Each case begins with one line with one integers m : the limit distance of substring.
Then a string S follow.

Limits

T≤100

0≤m≤5000
Each character in the string is lowercase letter,

2≤|S|≤5000

∑|S|≤20000

Output

For each test case output one interge denotes the answer : the maximum length of the substring.

Sample Input

1
5
abcdefedcb

Sample Output

5

Hint
[0, 4] abcde
[5, 9] fedcb
The distance between them is abs('a' - 'b') + abs('b' - 'c') + abs('c' - 'd') + abs('d' - 'e') + abs('e' - 'f') = 5
 

Source

2017 Multi-University Training Contest - Team 6

Recommend

liuyiding | We have carefully selected several similar problems for you: 6107 6106 6105 6104 6103

Statistic | Submit | Discuss | Note

题意：已知字符串S，要求不重叠的最长子串长度，并满足两子串距离最大不超过m

/*
思路：由于字符串很短，所以可以枚举前缀和后缀
在枚举的子串内采用尺取法将区间等分，利用sum不大于m的条件双指针同时遍历两个区间，更新最大值即可

*/
#include<bits/stdc++.h>
#include<iostream>
#include<stdio.h>
using namespace std;


const int maxn=5e3+10;
int m,nl,ans;//nl表示字符串长度，ans代表最后返回的子串长度
char s[maxn];

void solve()
{
    for(int i=2;i<=nl;i++)//i表示从总串中取出的子串长度
    {
        int o=i/2;
        int l=0,n=0,sum=0;
        for(int j=0;j<o;j++)
        {
            sum+=abs(s[j]-s[i-j-1]);
            if(sum<=m)n++,ans=max(ans,n);
            else
            {
                sum-=abs(s[l]-s[i-l-1]);
                sum-=abs(s[j]-s[i-j-1]);
                l++;
                j--;
                n--;
            }
        }
    }
}



int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d %s",&m,s);
        nl=strlen(s);
        ans=0;
        solve();
        reverse(s,s+nl);
        solve();
        printf("%d
",ans);

    }
    return 0;
}