题目描述

给定一个由小写字母构成的字符串。

如果一个字母在字符串中出现不止一次，就称它是重字母，否则就称它是轻字母。

给定 $T$ 个长度为 $N$ 的字符串，请你判断每个字符串是否是轻重交替结构。

如果一个字符串中的任意两个相邻字符都不同为重或同为轻，就称该字符串为轻重交替结构。

输入格式

第一行包含整数 $T$ ， $N$ 。

接下来 $T$ 行，每行包含一个长度为 $N$ 的由小写字母构成的字符串。

输出格式

共 $T$ 行，其中第 $i$ 行输出对第 $i$ 个字符串的判断，如果是轻重交替结构，则输出T，否则输出F。

样例

样例输入#1

3 4
abcb
bcbb
babc

样例输出#1

T
F
T

样例输入#2

2 3
abc
bcb

样例输出#2

F
T

数据范围与约定

$2 \leq T \leq 10000$ ， $2 \leq N \leq 100$ 。

思路

对于每一个字符串，考虑便利每一个字符并距记录每一个字符出现的次数，并重新遍历每一个字符，检查相邻两个字符是否轻重交替。

使用数组 $cnt$ 来表示每个字符出现的时间。遍历每一个字符串过程如下：

for (int i = 0; i < n; i++)
{
    cnt[str[i] - 'a']++;
}

在记录每一个字母的出现次数后，再重新遍历一次字符串并检查两个字符是否轻重交替。使用 $ok$ 来表示字符串是否轻重交替。 $ok$ 初始化为真。

当两个字符不是轻重交替时，可能出现一下两种情况：

1、当两个字符都为轻字母，即两个字母都只出现了一次：

if (cnt[str[i] - 'a'] == 1 && cnt[str[i + 1] - 'a'] == 1)
{
    ok = false;
}

2、当两个字符都为重字母，即两个字母的出现次数均大于 $1$ ：

if (cnt[str[i] - 'a'] > 1 && cnt[str[i + 1] - 'a'] > 1)
{
    ok = false;
}

在遍历每一个字符时，只需要从第一个开始一直遍历至倒数第二个。这样保证每一个相邻的两个字母都被遍历过。如果发现有任何两个相邻字符不是轻重交替，则可以退出遍历。结合上述检查是否轻重交替的代码，整个检查过程如下：

for (int i = 0; i < n - 1; i++)
{
    if ((cnt[str[i] - 'a'] == 1 && cnt[str[i + 1] - 'a'] == 1) ||
        (cnt[str[i] - 'a'] > 1 && cnt[str[i + 1] - 'a'] > 1))
    {
        ok = false;

        break;
    }
}

C++

#include <iostream>
#include <cstring>

using namespace std;

int t, n;

int main()
{
    cin >> t >> n;

    while (t--)
    {
        int cnt[26];
        bool ok = true;
        string str;

        memset(cnt, 0, sizeof(cnt));

        cin >> str;

        for (int i = 0; i < n; i++)
        {
            cnt[str[i] - 'a']++;
        }

        for (int i = 0; i < n - 1; i++)
        {
            if ((cnt[str[i] - 'a'] == 1 && cnt[str[i + 1] - 'a'] == 1) ||
                (cnt[str[i] - 'a'] > 1 && cnt[str[i + 1] - 'a'] > 1))
            {
                ok = false;

                break;
            }
        }

        if (ok)
        {
            cout << 'T' << endl;
        }
        else
        {
            cout << 'F' << endl;
        }
    }

    return 0;
}