首页 > 代码库 > codeforces A. k-String 题解

codeforces A. k-String 题解

2024-07-02 16:47:13   224人阅读

A string is called a k-string if it can be represented as k concatenated copies of some string. For example, the string "aabaabaabaab" is at the same time a 1-string, a 2-string and a 4-string, but it is not a 3-string, a 5-string, or a 6-string and so on. Obviously any string is a 1-string.

You are given a string s, consisting of lowercase English letters and a positive integer k. Your task is to reorder the letters in the string s in such a way that the resulting string is a k-string.

Input

The first input line contains integer k (1?≤?k?≤?1000). The second line contains s, all characters in s are lowercase English letters. The string length s satisfies the inequality 1?≤?|s|?≤?1000, where |s| is the length of string s.

Output

Rearrange the letters in string s in such a way that the result is a k-string. Print the result on a single output line. If there are multiple solutions, print any of them.

If the solution doesn‘t exist, print "-1" (without quotes).

Sample test(s)
input
2
aazz
output
azaz
input
3
abcabcabz
output
-1

本题有意思，是hash表的灵活运用。

思路：

1 计算好总字符数，和使用hash表A[26]记录好各个字符出现的次数

2 判断总字符是否可以被k整除，如果不可以，那么就不能分成k个子字符了

3 计算各个字符出现的次数是否能被k整除，如果不能，那么就不能分成k个子字符

4 根据字符出现的次数逐个打印

#include <string>
#include <iostream>
using namespace std;

void KString()
{
	int k, len = 0;
	cin>>k;
	int A[26] = {0};
	char a;
	while (cin>>a)
	{
		A[a-‘a‘]++;
		len++;
	}
	if (len == 0 || len % k) 
	{
		cout<<-1;
		return;
	}

	bool ks = true;
	for (unsigned i = 0; i < 26; i++)
	{
		if (A[i] % k != 0) ks = false;
	}
	if (!ks) cout<<-1;
	else
	{
		for (int d = 0; d < k; d++)
		{
			for (unsigned i = 0; i < 26; i++)
			{
				if (A[i])
					for (unsigned j = 0; j < A[i]/k; j++)
					{
						cout<<char(i + ‘a‘);
					}
			}
		}
	}
}


联系
我们