Problem Statement
Hero has an infinite periodic string t. You are given the string s that is the period of Hero's string. For example, if s = "abc", Hero's actual string is t = "abcabcabcabc…" Let n be the length of string s. Hero is now going to use the infinite string t to generate a new n-character string by doing the following steps:
He will choose an offset: a non-negative integer x.
He will choose the length of a step: a prime number p that is less than n.
The new string will consists of the first n characters we can read in the string t if we start at the index x and after each character we move p positions to the right.
Formally, Hero's new string will consist of the following characters, in order: t[x], t[x + p], t[x + 2p], …, t[x + (n-1)p]. Find and return the lexicographically smallest string Hero can produce.
Definition
Class: RingLex
Method: getmin
Parameters: string
Returns: string
Method signature: string getmin(string s)
(be sure your method is public)
Limits
Time limit (s): 2.000
Memory limit (MB): 256
Stack limit (MB): 256
Notes
Given two distinct strings of the same length, the lexicographically smaller one is the one that has a smaller character at the first position where they differ.
A positive integer p is a prime if it has exactly two distinct divisors: 1 and p. Note that the number 1 is not a prime.
Constraints
s will contain between 3 and 50 characters, inclusive.
Each character in s will be between 'a' and 'z', inclusive.
Examples
分析
本题要求最小的字符串,可以考虑使用set来存放所有的字符串。因为set是默认是按从小到大的顺序排列的,最终咱们取出set里的第一个字符串即为所求。
本题的数据量不大,直接穷举即可。
代码
领取专属 10元无门槛券
私享最新 技术干货