Connection Status:
Competition Arena > DoubleLetter

DoubleLetter

SRM 630 · 2014-07-26 · by cgy4ever

SRM 630 · 2014-07-26 · by cgy4ever · Greedy
Class Name: DoubleLetter
Return Type: String
Method Name: ableToSolve
Arg Types: (string)
Problem Statement

Problem Statement

You are given a String S. You can modify this string by repeating the following process:
  1. Find the leftmost occurrence of two consecutive letters in S that are the same.
  2. If you found a pair of identical letters in the first step, delete those two letters from S.
For example, if S="aabccb", you can proceed as follows:
  1. Find and erase "aa", producing the string "bccb".
  2. Find and erase "cc", producing the string "bb".
  3. Find and erase "bb", producing the empty string.
For S="axxyybac" you can do at most two steps, erasing "xx" first and "yy" next. Once you obtain the string "abac", you are done. Note that you cannot erase the two "a"s because they are not consecutive. You want to change S into an empty string by repeating the operation described above. Return "Possible" if you can do that, and "Impossible" otherwise.

Constraints

  • S will contain between 1 and 50 characters.
  • Each character in S will be a lowercase English letter ('a'-'z').
Examples
0)
"aabccb"
Returns: "Possible"
1)
"aabccbb"
Returns: "Impossible"

The process will terminate with a single 'b'.

2)
"abcddcba"
Returns: "Possible"

"abcddcba" -> "abccba" -> "abba" -> "aa" -> "".

3)
"abab"
Returns: "Impossible"

No two successive letters are the same, so we can't do any operation.

4)
"aaaaaaaaaa"
Returns: "Possible"

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

Coding Area

Language: C++17 · define a public class DoubleLetter with a public method string ableToSolve(string S) · 106 test cases · 2 s / 256 MB per case

Submitting as anonymous