Connection Status:
Competition Arena > AlphabetOrderDiv2

AlphabetOrderDiv2

SRM 705 Sponsored By Blizzard · 2016-12-22 · by ltaravilse

SRM 705 Sponsored By Blizzard · 2016-12-22 · by ltaravilse · Sorting
Class Name: AlphabetOrderDiv2
Return Type: String
Method Name: isOrdered
Arg Types: (vector<string>)
Problem Statement

Problem Statement

The ancient civilization of Nlogonia used the same 26 letters as modern English: 'a'-'z'. However, we do not know the order in which these letters appeared in the Nlogonian alphabet.
One particular custom in Nlogonia was that in a good word the letters appear in non-decreasing order. For example, in English the word "ciel" is not a good word because in the alphabet 'i' is after 'e'. The word "ceil" is a good word because 'c' <= 'e' <= 'i' <= 'l'.
You are given the String[] words. Each element of words is a nonempty string of lowercase English letters. Return "Possible" if it is possible that all elements of words were good words in Nlogonian, and "Impossible" otherwise.
In other words, return "Possible" if and only if there is at least one possible Nlogonian alphabet such that the letters of each word in words are in non-decreasing alphabetical order.

Constraints

  • words has between 2 and 100 elements inclusive.
  • The size of each element of words will be between 1 and 100 inclusive.
  • Elements of words contains only English lowercase letters from 'a' to 'z'.
Examples
0)
{"single","round","match"}
Returns: "Possible"

One possible Nlogonian alphabet is "bfjkmapqrositchundglevwxyz".

1)
{"topcoder","topcoder"}
Returns: "Impossible"

The word "topcoder" can never be a good word. The character 'o' cannot be both before 'p' and after 'p' in the alphabet.

2)
{"algorithm", "contest"}
Returns: "Impossible"
3)
{"pink","floyd"}
Returns: "Possible"
4)
{"gimnasia","y","esgrima","la","plata"}
Returns: "Impossible"
5)
{"hello","hello"}
Returns: "Possible"

This is a good word for any alphabet in which the letters 'h', 'e', 'l', and 'o' appear in this order.

6)
{"abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"}
Returns: "Possible"

In this case the English alphabet is one of the valid permutations.

7)
{"abc","bca"}
Returns: "Impossible"

'a' must come before 'c' (because of the first name) and after 'c' (because of the second name) and that is a contradiction. Thus, there is no valid solution.

8)
{"aaaaa","eeeee","iiiii","ooooo","uuuuu"}
Returns: "Possible"

Any order is valid in this case

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

Coding Area

Language: C++17 · define a public class AlphabetOrderDiv2 with a public method string isOrdered(vector<string> words) · 78 test cases · 2 s / 256 MB per case

Submitting as anonymous