Cyclemin

SRM 660 · 2015-05-01 · by subscriber

SRM 660 · 2015-05-01 · by subscriber · Brute Force

Show categories

Class Name: Cyclemin

Return Type: String

Method Name: bestmod

Arg Types: (string, int)

Problem Statement

A rotation of a string S is the operation of moving its first character to the end. For example, if we rotate the string "abcde" we get the string "bcdea".

A cyclic shift of a string S is any string that can be obtained from S by a sequence of zero or more rotations. For example, the strings "abcde", "cdeab", and "eabcd" are some of the cyclic shifts of the string "abcde".

Given two equally long strings, the smaller one is the one with a smaller character at the first index where they differ. For example, "cable" < "cards" because 'b' < 'r'.

You are given a String s of lowercase letters and an int k. You are allowed to change at most k letters of s into some other lowercase letters.

Your goal is to create a string that will have the smallest possible cyclic shift. Compute and return that cyclic shift.

Constraints

s will contain between 1 and 50 characters, inclusive.
Each character in s will be between 'a' and 'z', inclusive.
k will be between 0 and the length of s, inclusive.

Examples

"aba"
1
Returns: "aaa"

We are allowed to change at most 1 character. Clearly, the optimal change is to change the 'b' into an 'a'.

"aba"
0
Returns: "aab"

We are not allowed to change anything. In this case, the answer is the smallest cyclic shift of the given string s.

"bbb"
2
Returns: "aab"

"sgsgaw"
1
Returns: "aasgsg"

The optimal solution is to change the 'w' into an 'a', and then to take the cyclic shift that starts with the last two letters of s.

"abacaba"
1
Returns: "aaaabac"

Submissions are judged against all 128 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class Cyclemin with a public method string bestmod(string s, int k) · 128 test cases · 2 s / 256 MB per case