StringsBetween
SRM 789 · 2020-08-28 · by misof
Problem Statement
All strings in this problem are strings of 0 to L lowercase English characters. We will call them valid strings.
All string comparisons are standard comparisons according to their lexicographic order: the string with a smaller character at the leftmost index on which they differ is smaller (e.g., "car" < "cat" because 'r' < 't') and if X is a prefix of Y, X is smaller than Y (e.g., "cat" < "cats").
You are given two valid strings A and B such that A < B.
Return the number of valid strings C such that A < C < B.
Constraints
- L will be between 0 and 10, inclusive.
- A and B will be valid strings.
- A will be less than B.
1 "" "d" Returns: 3
The valid strings between "" and "d" are "a", "b", and "c".
2 "ay" "c" Returns: 28
The valid strings are "az", "b", "ba", "bb", ..., "bx", "by", "bz".
2 "ay" "cb" Returns: 30
Compared to the previous example we now also have valid strings "c" and "ca" within the specified range.
10 "bulldog" "bulldozers" Returns: 350592
4 "bx" "fad" Returns: 57028
10 "" "zzzzzzzzzz" Returns: 146813779479509
The largest possible output.
Submissions are judged against all 17 archived test cases, of which 6 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class StringsBetween with a public method long long count(int L, string A, string B) · 17 test cases · 2 s / 256 MB per case