Connection Status:
Competition Arena > CorruptedMessage

CorruptedMessage

SRM 656 · 2015-03-26 · by lg5293

SRM 656 · 2015-03-26 · by lg5293 · Brute Force
Class Name: CorruptedMessage
Return Type: String
Method Name: reconstructMessage
Arg Types: (string, int)
Problem Statement

Problem Statement

Your friend just sent you a message. The message consisted of one or more copies of the same lowercase letter. For example, "aaaaa" and "xxxxxxxxx" are valid messages. Unfortunately, on its way to you the message became corrupted: exactly k letters of the original message were changed to some other letters. The message you received is s.

Given the String s and the int k, reconstruct the original message. More precisely, return a String that could have been the original message. It is guaranteed that at least one such String will always exist. If there are multiple possible answers, you may return any of them.

Constraints

  • The number of characters in s will be between 1 and 50, inclusive.
  • Each character in s will be a lowercase letter ('a'-'z').
  • k will be between 0 and the length of s, inclusive.
  • At least one possible original message will be consistent with s and k.
Examples
0)
"hello"
3
Returns: "lllll"

The three corrupted characters have 0-based indices 0, 1, and 4.

1)
"abc"
3
Returns: "ddd"

The original message can't be "aaa", "bbb", or "ccc", since we need to change exactly 3 characters. Some other possible answers include "qqq", "xxx", or "ppp".

2)
"wwwwwwwwwwwwwwwwww"
0
Returns: "wwwwwwwwwwwwwwwwww"

No characters were corrupted.

3)
"ababba"
3
Returns: "aaaaaa"

"bbbbbb" will also be accepted.

4)
"zoztxtoxytyt"
10
Returns: "oooooooooooo"

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

Coding Area

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

Submitting as anonymous