CF1547B Alphabetical Strings（了解字符串的的一些规律）

Alphabetical Strings

time limit per test2 seconds

memory limit per test512 megabytes

inputstandard input

outputstandard output

A string s of length n (1≤n≤26) is called alphabetical if it can be obtained using the following algorithm:

first, write an empty string to s (i.e. perform the assignment s := “”);

then perform the next step n times;

at the i-th step take i-th lowercase letter of the Latin alphabet and write it either to the left of the string s or to the right of the string s (i.e. perform the assignment s := c+s or s := s+c, where c is the i-th letter of the Latin alphabet).

In other words, iterate over the n first letters of the Latin alphabet starting from ‘a’ and etc. Each time we prepend a letter to the left of the string s or append a letter to the right of the string s. Strings that can be obtained in that way are alphabetical.

For example, the following strings are alphabetical: “a”, “ba”, “ab”, “bac” and “ihfcbadeg”. The following strings are not alphabetical: “z”, “aa”, “ca”, “acb”, “xyz” and “ddcba”.

From the given string, determine if it is alphabetical.

Input

The first line contains one integer t (1≤t≤10^4) — the number of test cases. Then t test cases follow.

Each test case is written on a separate line that contains one string s. String s consists of lowercase letters of the Latin alphabet and has a length between 1 and 26, inclusive.

Output

Output t lines, each of them must contain the answer to the corresponding test case. Output YES if the given string s is alphabetical and NO otherwise.

You can output YES and NO in any case (for example, strings yEs, yes, Yes and YES will be recognized as a positive answer).

Example

inputCopy

11

a

ba

ab

bac

ihfcbadeg

z

aa

ca

acb

xyz

ddcba

outputCopy

YES

YES

YES

YES

YES

NO

NO

NO

NO

NO

NO

Note

The example contains test cases from the main part of the condition.

题意分析

生成一个字符串（字符都是小写字母）。生成规则如下：

·初始字符串是空的。

·每次在前面或后面加入一个字符，第 ii 次加入的字符是小写字母表中第 ii 个小写字母。

给一些字符串，请判断是否可以被生成出来。

做法

显然若字符串中字符的出现并不连续或者同一个字符出现了两次，那么该串是不行的。

举个栗子：dba，bab。

然后我们看：每次字母从小到大加，且加在两侧，那是不是中间的字符会比旁边的小呢？

有了这些结论，这题就做完了，上代码。

#include<bits/stdc++.h>
using namespace std;
int main()
{
  int t;
  cin>>t;
  while(t--)
  {
    string s;
    cin>>s;
    int l=0;
    int r=s.size()-1;
    while(l<=r)
    {
      if((s[l]-'a')==r-l)
      l++;
      else if((s[r]-'a')==r-l)
      r--;
      else break; 
    }
    if(l>r)
    cout<<"YES"<<endl;
    else
    cout<<"NO"<<endl; 
  }
 }