Connection Status:
Competition Arena > CompletelyDifferentStrings

CompletelyDifferentStrings

SRM 775 · 2020-01-15 · by misof

SRM 775 · 2020-01-15 · by misof · Simple Math, Simple Search, Iteration, String Manipulation
Class Name: CompletelyDifferentStrings
Return Type: int
Method Name: count
Arg Types: (int, vector<string>)
Problem Statement

Problem Statement

You are given an int S and a String[] forbidden. The strings in forbidden only use the first S lowercase English letters, and all these strings have the same length L.

Two strings of length L are called completely different if they differ at every index. For example, X="abcd" and Y="bcda" are completely different but X="frog" and Y="plow" are not because X[2] = Y[2] = 'o'.

Compute and return the total number of strings with the following properties:

  • The length of the string is L. (That is, its length is the same as the length of the strings in forbidden.)
  • Each character of the string is one of the first S lowercase English letters.
  • The string is completely different from every string in forbidden.

Constraints

  • S will be between 1 and 26, inclusive.
  • forbidden will contain between 1 and 30 elements, inclusive.
  • All elements of forbidden will have the same length L.
  • L will be between 1 and 6, inclusive.
  • Each character in each element of forbidden will be one of the first S lowercase English letters.
Examples
0)
3
{"ab"}
Returns: 4

As S = 3, we are only using the first three lowercase English letters: 'a', 'b', and 'c'. We are looking for strings of length 2 that are completely different from "ab". There are four such strings: "ba", "bc", "ca", and "cc".

1)
1
{"aaaaa", "aaaaa"}
Returns: 0

The only string of length 5 is "aaaaa", but this string is not completely different from the (identical) forbidden string "aaaaa". Thus, there are no strings with all the properties we need.

2)
2
{"ababa", "babab"}
Returns: 0
3)
2
{"ababa", "abbba"}
Returns: 0
4)
7
{"baba", "babe", "cage", "cafe", "feed", "deed", "deaf", "dead"}
Returns: 90
5)
3
{"abacaa", "abacaa", "acabab"}
Returns: 8

Note that the strings in forbidden are not necessarily distinct.

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

Coding Area

Language: C++17 · define a public class CompletelyDifferentStrings with a public method int count(int S, vector<string> forbidden) · 113 test cases · 2 s / 256 MB per case

Submitting as anonymous