Connection Status:
Competition Arena > LexOrder

LexOrder

TCO19 SRM 750 · 2019-01-09 · by misof

TCO19 SRM 750 · 2019-01-09 · by misof · Brute Force, String Manipulation
Class Name: LexOrder
Return Type: String
Method Name: between
Arg Types: (string, string)
Problem Statement

Problem Statement

In this problem, all strings are strings of lowercase English letters ('a'-'z').

You are given the Strings A and B such that A < B. If there is a string C such that A < C < B, return any such string. (The returned string C must have at most 50 characters, and each character of C must be a lowercase English letter.) If there is no such string C, return the string "IMPOSSIBLE" instead.

 

Below, we define how to compare two strings. This definition is the standard one and we include it just to have a complete, self-contained problem statement. If you already know how string comparison works, you do not have to read it.

Suppose S and T are two distinct strings. We say that S is smaller than T in lexicographic order (denoted S < T) if:

  1. either S is a proper prefix of T,
  2. or there is some i >= 0 such that:
    1. the first i characters of S are the same as the first i characters of T
    2. the next character of S is smaller than the next character of T

For example:

  • "car" < "careful" because "car" is a proper prefix of "careful"
  • "dog" < "donut" because the first two characters of both strings are the same ("do") and 'g' is smaller than 'n'.

Notes

  • The statements "character x is smaller than character y", "character x is earlier in the alphabet than character y", and "character x has a smaller ASCII code than character y" are equivalent.
  • The return value is case-sensitive. The string IMPOSSIBLE must be in all-uppercase.

Constraints

  • A will have between 1 and 10 characters, inclusive.
  • B will have between 1 and 10 characters, inclusive.
  • Each character of A and B will be a lowercase English letter ('a'-'z').
  • A will be lexicographically smaller than B.
Examples
0)
"car"
"dog"
Returns: "careful"

Other valid return values include "ceiling", "catastrophiccancellation", "darling", "do", and "dododododo".

1)
"car"
"cat"
Returns: "cash"
2)
"abcdefghij"
"abcdefghik"
Returns: "abcdefghijklmnopqrst"

Note that the input strings always have at most 10 characters but the string you return may be longer (up to 50 characters).

3)
"man"
"mana"
Returns: "IMPOSSIBLE"
4)
"a"
"ab"
Returns: "aa"

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

Coding Area

Language: C++17 · define a public class LexOrder with a public method string between(string A, string B) · 94 test cases · 2 s / 256 MB per case

Submitting as anonymous