NewArenaPassword
SRM 572 · 2012-12-13 · by fushar
SRM 572 · 2012-12-13 · by fushar · Greedy
Problem Statement
Problem Statement
You are a huge fan of an online programming contest called SRM (Special Round Match). To participate in an SRM contest, you must first download an applet called Arena, log in to the Arena by entering your username and password, and start competing.
Recently, to avoid hackers' attacks on the Arena, SRM imposes a new rule for the users' passwords. From now on, the first K characters of each user's password must match its last K characters. In this way, if someone enters a password with different first and last K characters repeatedly, it can be considered an attack from hackers.
However, you love your old password and do not want to change many characters from it. You are given aString oldPassword representing your old password, and an int K. Return the minimum number of characters of oldPassword that must be changed so that the string containing the first K characters of oldPassword is equal to the string containing the last K characters of oldPassword.
Recently, to avoid hackers' attacks on the Arena, SRM imposes a new rule for the users' passwords. From now on, the first K characters of each user's password must match its last K characters. In this way, if someone enters a password with different first and last K characters repeatedly, it can be considered an attack from hackers.
However, you love your old password and do not want to change many characters from it. You are given a
Constraints
- oldPassword will contain between 1 and 50 characters, inclusive.
- Each character of oldPassword will be a lowercase letter 'a' - 'z'.
- K will be between 1 and the number of characters of oldPassword, inclusive.
Examples
0)
"topcoderopen" 5 Returns: 3
A possible solution is changing your password into "topcndetopcn". To do this, you must change the 4th, 7th, and 10th characters (0-based) of "topcoderopen".
1)
"puyopuyo" 4 Returns: 0
Your old password already satisfies the new rule.
2)
"loool" 3 Returns: 1
The first and the last K characters can overlap. In this case, the only optimal solution is to change your password into "lolol".
3)
"arena" 5 Returns: 0
4)
"amavckdkz" 7 Returns: 5
Submissions are judged against all 186 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class NewArenaPassword with a public method int minChange(string oldPassword, int K) · 186 test cases · 2 s / 256 MB per case