StringTransform

SRM 711 · 2017-02-20 · by Arterm

SRM 711 · 2017-02-20 · by Arterm · Greedy, Simple Search, Iteration

Show categories

Class Name: StringTransform

Return Type: String

Method Name: isPossible

Arg Types: (string, string)

Problem Statement

You are given the Strings s and t. Both strings have the same length.

You are allowed to modify s. In each step you may choose two valid indices i and j such that i > j, and change s[i] to s[j]. For example, if s = "abc", you may choose i=2 and j=0, which will change s to "aba".

Return "Possible" (quotes for clarity) if you can change s into t by a sequence of zero or more steps. Otherwise, return "Impossible".

Note that the return values are case-sensitive.

Constraints

s will contain between 1 and 1,000 characters, inclusive.
s and t will be of equal length.
s will contain only lowercase English letters.
t will contain only lowercase English letters.

Examples

"abc"
"aba"
Returns: "Possible"

This is the example from the problem statement. We can change s into t by changing s[2] to s[0].

"abc"
"bbc"
Returns: "Impossible"

Note that in each step i must be greater than j. You are not allowed to choose i=0 and j=1.

"topcoder"
"topcoder"
Returns: "Possible"

The two strings are equal, so we don't have to make any changes.

"rdmcxnnbbe"
"rdrrxrnxbe"
Returns: "Possible"

"rdmcxnnbbe"
"rdqrxrnxbe"
Returns: "Impossible"

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

Coding Area

Language: C++17 · define a public class StringTransform with a public method string isPossible(string s, string t) · 56 test cases · 2 s / 256 MB per case