CodeForces 1251A --- Broken Keyboard-有解無憂

【CodeForces 1251A --- Broken Keyboard 】

Description

Recently Polycarp noticed that some of the buttons of his keyboard are malfunctioning. For simplicity, we assume that Polycarp’s keyboard contains 26 buttons (one for each letter of the Latin alphabet). Each button is either working fine or malfunctioning.

To check which buttons need replacement, Polycarp pressed some buttons in sequence, and a string s appeared on the screen. When Polycarp presses a button with character c, one of the following events happened:

if the button was working correctly, a character c appeared at the end of the string Polycarp was typing;
if the button was malfunctioning, two characters c appeared at the end of the string.
For example, suppose the buttons corresponding to characters a and c are working correctly, and the button corresponding to b is malfunctioning. If Polycarp presses the buttons in the order a, b, a, c, a, b, a, then the string he is typing changes as follows: a → abb → abba → abbac → abbaca → abbacabb → abbacabba.

You are given a string s which appeared on the screen after Polycarp pressed some buttons. Help Polycarp to determine which buttons are working correctly for sure (that is, this string could not appear on the screen if any of these buttons was malfunctioning).

You may assume that the buttons don’t start malfunctioning when Polycarp types the string: each button either works correctly throughout the whole process, or malfunctions throughout the whole process.

Input

The first line contains one integer t (1≤t≤100) — the number of test cases in the input.

Then the test cases follow. Each test case is represented by one line containing a string s consisting of no less than 1 and no more than 500 lowercase Latin letters.

Output

For each test case, print one line containing a string res. The string res should contain all characters which correspond to buttons that work correctly in alphabetical order, without any separators or repetitions. If all buttons may malfunction, res should be empty.

Sample Input

4
a
zzaaz
ccff
cbddbb

Sample Output

a
z

bc

解體思路：壞的按鍵會出現2次，好的按鍵出現1次，一開始想的是只要統計字母的所有出現次數，如果是奇數那么就是好的按鍵，仔細一想發現是錯的，如果出現asssaaa,那么就會出錯，那么應該統計的是連續的一段相同字母的個數，如果是奇數則是正確的，

AC代碼：

#include <iostream>
#include <cstring>
#include <string>
using namespace std;
int main()
{
    string str;
    int n;
    int num[1005];
    cin>>n;
    while(n--)
    {
        int cnt=1;
        memset(num,0,sizeof num);
        cin>>str;
        for(int i=1;i<=str.length();i++)
        {
            if(str[i]==str[i-1])    
                cnt++;
            else
            {
                if(cnt%2==1)
                    num[str[i-1]-'a']=1;
                cnt=1;
            }
        }
        for(int i=0;i<26;i++)
        {
            if(num[i]==1)
                cout<<char(i+'a');
        }
        cout<<endl;
    }
    return 0;
}

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/136665.html

標籤：其他

上一篇：【LeetCode】6. Z 字形變換

下一篇：leetcode不同路徑